home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 15 / AACD15.ISO / AACD / Programming / Python2 / Python20_source / Modules / parsermodule.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-10-25  |  81.5 KB  |  2,831 lines
  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
  42. char *strdup(char *);
  43. #endif
  44.  
  45. /*  String constants used to initialize module attributes.
  46.  *
  47.  */
  48. static char*
  49. parser_copyright_string
  50. = "Copyright 1995-1996 by Virginia Polytechnic Institute & State\n\
  51. University, Blacksburg, Virginia, USA, and Fred L. Drake, Jr., Reston,\n\
  52. Virginia, USA.  Portions copyright 1991-1995 by Stichting Mathematisch\n\
  53. Centrum, Amsterdam, The Netherlands.";
  54.  
  55.  
  56. static char*
  57. parser_doc_string
  58. = "This is an interface to Python's internal parser.";
  59.  
  60. static char*
  61. parser_version_string = "0.5";
  62.  
  63.  
  64. typedef PyObject* (*SeqMaker) (int length);
  65. typedef 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.  
  79. static PyObject*
  80. node2tuple(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.  
  155. static PyObject*
  156. parser_error = 0;
  157.  
  158.  
  159. typedef 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.  
  166. staticforward void
  167. parser_free(PyAST_Object *ast);
  168.  
  169. staticforward int
  170. parser_compare(PyAST_Object *left, PyAST_Object *right);
  171.  
  172. staticforward PyObject *
  173. parser_getattr(PyObject *self, char *name);
  174.  
  175.  
  176. static
  177. PyTypeObject 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.  
  208. static int
  209. parser_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.  */
  245. static int
  246. parser_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.  */
  265. static PyObject*
  266. parser_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.  */
  286. static void
  287. parser_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.  */
  300. static PyObject*
  301. parser_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.  */
  338. static PyObject*
  339. parser_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.  */
  375. static PyObject*
  376. parser_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.  */
  405. static PyObject*
  406. parser_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.  
  428. static PyObject*
  429. parser_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.  
  453. static PyMethodDef
  454. parser_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.  
  470. static PyObject*
  471. parser_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.  */
  482. static void
  483. err_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.  */
  495. static PyObject*
  496. parser_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.  */
  525. static PyObject*
  526. parser_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.  
  533. static PyObject*
  534. parser_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.  
  559. staticforward node* build_node_tree(PyObject *tuple);
  560. staticforward int   validate_expr_tree(node *tree);
  561. staticforward 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.  */
  577. static PyObject*
  578. parser_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.  */
  635. static node*
  636. build_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.  
  739. static node*
  740. build_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.  */
  786. staticforward 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.  
  807. VALIDATER(node);                VALIDATER(small_stmt);
  808. VALIDATER(class);               VALIDATER(node);
  809. VALIDATER(parameters);          VALIDATER(suite);
  810. VALIDATER(testlist);            VALIDATER(varargslist);
  811. VALIDATER(fpdef);               VALIDATER(fplist);
  812. VALIDATER(stmt);                VALIDATER(simple_stmt);
  813. VALIDATER(expr_stmt);           VALIDATER(power);
  814. VALIDATER(print_stmt);          VALIDATER(del_stmt);
  815. VALIDATER(return_stmt);         VALIDATER(list_iter);
  816. VALIDATER(raise_stmt);          VALIDATER(import_stmt);
  817. VALIDATER(global_stmt);         VALIDATER(list_if);
  818. VALIDATER(assert_stmt);         VALIDATER(list_for);
  819. VALIDATER(exec_stmt);           VALIDATER(compound_stmt);
  820. VALIDATER(while);               VALIDATER(for);
  821. VALIDATER(try);                 VALIDATER(except_clause);
  822. VALIDATER(test);                VALIDATER(and_test);
  823. VALIDATER(not_test);            VALIDATER(comparison);
  824. VALIDATER(comp_op);             VALIDATER(expr);
  825. VALIDATER(xor_expr);            VALIDATER(and_expr);
  826. VALIDATER(shift_expr);          VALIDATER(arith_expr);
  827. VALIDATER(term);                VALIDATER(factor);
  828. VALIDATER(atom);                VALIDATER(lambdef);
  829. VALIDATER(trailer);             VALIDATER(subscript);
  830. VALIDATER(subscriptlist);       VALIDATER(sliceop);
  831. VALIDATER(exprlist);            VALIDATER(dictmaker);
  832. VALIDATER(arglist);             VALIDATER(argument);
  833. VALIDATER(listmaker);
  834.  
  835. #undef VALIDATER
  836.  
  837. #define is_even(n)      (((n) & 1) == 0)
  838. #define is_odd(n)       (((n) & 1) == 1)
  839.  
  840.  
  841. static int
  842. validate_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.  */
  860. static int
  861. validate_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.  
  872. static int
  873. validate_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.  */
  888. static int
  889. validate_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.  */
  917. static int
  918. validate_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.  */
  943. static int
  944. validate_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.  */
  985. static int
  986. validate_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.  */
  1010. static int
  1011. validate_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.  
  1038. static int
  1039. validate_testlist(node *tree)
  1040. {
  1041.     return (validate_repeating_list(tree, testlist,
  1042.                                     validate_test, "testlist"));
  1043. }
  1044.  
  1045.  
  1046. /* '*' NAME [',' '**' NAME] | '**' NAME
  1047.  */
  1048. static int
  1049. validate_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.  */
  1094. static int
  1095. validate_varargslist(node *tree)
  1096. {
  1097.     int nch = NCH(tree);
  1098.     int res = validate_ntype(tree, varargslist) && (nch != 0);
  1099.     int sym;
  1100.  
  1101.     if (nch < 1) {
  1102.         err_string("varargslist missing child nodes");
  1103.         return 0;
  1104.     }
  1105.     sym = TYPE(CHILD(tree, 0));
  1106.     if (sym == STAR || sym == DOUBLESTAR)
  1107.         res = validate_varargslist_trailer(tree, 0);
  1108.     else if (sym == fpdef) {
  1109.         int i = 0;
  1110.  
  1111.         sym = TYPE(CHILD(tree, nch-1));
  1112.         if (sym == NAME) {
  1113.             /*
  1114.              *   (fpdef ['=' test] ',')+
  1115.              *       ('*' NAME [',' '**' NAME]
  1116.              *     | '**' NAME)
  1117.              */
  1118.             /* skip over (fpdef ['=' test] ',')+ */
  1119.             while (res && (i+2 <= nch)) {
  1120.                 res = validate_fpdef(CHILD(tree, i));
  1121.                 ++i;
  1122.                 if (res && TYPE(CHILD(tree, i)) == EQUAL && (i+2 <= nch)) {
  1123.                     res = (validate_equal(CHILD(tree, i))
  1124.                            && validate_test(CHILD(tree, i+1)));
  1125.                     if (res)
  1126.                         i += 2;
  1127.                 }
  1128.                 if (res && i < nch) {
  1129.                     res = validate_comma(CHILD(tree, i));
  1130.                     if (res)
  1131.                         ++i;
  1132.                 }
  1133.             }
  1134.             /* handle '*' NAME [',' '**' NAME] | '**' NAME */
  1135.             if (res)
  1136.                 res = validate_varargslist_trailer(tree, i);
  1137.         }
  1138.         else {
  1139.             /*
  1140.              *  fpdef ['=' test] (',' fpdef ['=' test])* [',']
  1141.              */
  1142.             if (sym == COMMA) {
  1143.                 res = validate_comma(CHILD(tree, nch-1));
  1144.                 if (!res)
  1145.                     return 0;
  1146.                 --nch;
  1147.             }
  1148.             /*
  1149.              *  fpdef ['=' test] (',' fpdef ['=' test])*
  1150.              */
  1151.             res = validate_fpdef(CHILD(tree, 0));
  1152.             ++i;
  1153.             if (res && (i+2 < nch) && TYPE(CHILD(tree, 1)) == EQUAL) {
  1154.                 res = (validate_equal(CHILD(tree, 1))
  1155.                        && validate_test(CHILD(tree, 2)));
  1156.                 i += 2;
  1157.             }
  1158.             /*
  1159.              *  ... (',' fpdef ['=' test])*
  1160.              *  i ---^^^
  1161.              */
  1162.             while (res && (nch - i) >= 2) {
  1163.                 res = (validate_comma(CHILD(tree, i))
  1164.                        && validate_fpdef(CHILD(tree, i+1)));
  1165.                 i += 2;
  1166.                 if (res && (nch - i) >= 2
  1167.                     && TYPE(CHILD(tree, i)) == COMMA) {
  1168.                     res = (validate_comma(CHILD(tree, i))
  1169.                            && validate_test(CHILD(tree, i+1)));
  1170.                     if (res)
  1171.                         i += 2;
  1172.                 }
  1173.             }
  1174.             if (res && nch - i != 0) {
  1175.                 res = 0;
  1176.                 err_string("illegal formation for varargslist");
  1177.             }
  1178.         }
  1179.     }
  1180.     return res;
  1181. }
  1182.  
  1183.  
  1184. /*  list_iter:  list_for | list_if
  1185.  */
  1186. static int
  1187. validate_list_iter(node *tree)
  1188. {
  1189.     int res = (validate_ntype(tree, list_iter)
  1190.                && validate_numnodes(tree, 1, "list_iter"));
  1191.     if (res && TYPE(CHILD(tree, 0)) == list_for)
  1192.         res = validate_list_for(CHILD(tree, 0));
  1193.     else
  1194.         res = validate_list_if(CHILD(tree, 0));
  1195.  
  1196.     return res;
  1197. }
  1198.  
  1199. /*  list_for:  'for' exprlist 'in' testlist [list_iter]
  1200.  */
  1201. static int
  1202. validate_list_for(node *tree)
  1203. {
  1204.     int nch = NCH(tree);
  1205.     int res;
  1206.  
  1207.     if (nch == 5)
  1208.         res = validate_list_iter(CHILD(tree, 4));
  1209.     else
  1210.         res = validate_numnodes(tree, 4, "list_for");
  1211.  
  1212.     if (res)
  1213.         res = (validate_name(CHILD(tree, 0), "for")
  1214.                && validate_exprlist(CHILD(tree, 1))
  1215.                && validate_name(CHILD(tree, 2), "in")
  1216.                && validate_testlist(CHILD(tree, 3)));
  1217.  
  1218.     return res;
  1219. }
  1220.  
  1221. /*  list_if:  'if' test [list_iter]
  1222.  */
  1223. static int
  1224. validate_list_if(node *tree)
  1225. {
  1226.     int nch = NCH(tree);
  1227.     int res;
  1228.  
  1229.     if (nch == 3)
  1230.         res = validate_list_iter(CHILD(tree, 2));
  1231.     else
  1232.         res = validate_numnodes(tree, 2, "list_if");
  1233.  
  1234.     if (res)
  1235.         res = (validate_name(CHILD(tree, 0), "if")
  1236.                && validate_test(CHILD(tree, 1)));
  1237.  
  1238.     return res;
  1239. }
  1240.  
  1241.  
  1242. /*  validate_fpdef()
  1243.  *
  1244.  *  fpdef:
  1245.  *      NAME
  1246.  *    | '(' fplist ')'
  1247.  */
  1248. static int
  1249. validate_fpdef(node *tree)
  1250. {
  1251.     int nch = NCH(tree);
  1252.     int res = validate_ntype(tree, fpdef);
  1253.  
  1254.     if (res) {
  1255.         if (nch == 1)
  1256.             res = validate_ntype(CHILD(tree, 0), NAME);
  1257.         else if (nch == 3)
  1258.             res = (validate_lparen(CHILD(tree, 0))
  1259.                    && validate_fplist(CHILD(tree, 1))
  1260.                    && validate_rparen(CHILD(tree, 2)));
  1261.         else
  1262.             res = validate_numnodes(tree, 1, "fpdef");
  1263.     }
  1264.     return (res);
  1265. }
  1266.  
  1267.  
  1268. static int
  1269. validate_fplist(node *tree)
  1270. {
  1271.     return (validate_repeating_list(tree, fplist,
  1272.                                     validate_fpdef, "fplist"));
  1273. }
  1274.  
  1275.  
  1276. /*  simple_stmt | compound_stmt
  1277.  *
  1278.  */
  1279. static int
  1280. validate_stmt(node *tree)
  1281. {
  1282.     int res = (validate_ntype(tree, stmt)
  1283.                && validate_numnodes(tree, 1, "stmt"));
  1284.  
  1285.     if (res) {
  1286.         tree = CHILD(tree, 0);
  1287.  
  1288.         if (TYPE(tree) == simple_stmt)
  1289.             res = validate_simple_stmt(tree);
  1290.         else
  1291.             res = validate_compound_stmt(tree);
  1292.     }
  1293.     return (res);
  1294. }
  1295.  
  1296.  
  1297. /*  small_stmt (';' small_stmt)* [';'] NEWLINE
  1298.  *
  1299.  */
  1300. static int
  1301. validate_simple_stmt(node *tree)
  1302. {
  1303.     int nch = NCH(tree);
  1304.     int res = (validate_ntype(tree, simple_stmt)
  1305.                && (nch >= 2)
  1306.                && validate_small_stmt(CHILD(tree, 0))
  1307.                && validate_newline(CHILD(tree, nch - 1)));
  1308.  
  1309.     if (nch < 2)
  1310.         res = validate_numnodes(tree, 2, "simple_stmt");
  1311.     --nch;                              /* forget the NEWLINE    */
  1312.     if (res && is_even(nch))
  1313.         res = validate_semi(CHILD(tree, --nch));
  1314.     if (res && (nch > 2)) {
  1315.         int i;
  1316.  
  1317.         for (i = 1; res && (i < nch); i += 2)
  1318.             res = (validate_semi(CHILD(tree, i))
  1319.                    && validate_small_stmt(CHILD(tree, i + 1)));
  1320.     }
  1321.     return (res);
  1322. }
  1323.  
  1324.  
  1325. static int
  1326. validate_small_stmt(node *tree)
  1327. {
  1328.     int nch = NCH(tree);
  1329.     int res = validate_numnodes(tree, 1, "small_stmt");
  1330.  
  1331.     if (res) {
  1332.         int ntype = TYPE(CHILD(tree, 0));
  1333.  
  1334.         if (  (ntype == expr_stmt)
  1335.               || (ntype == print_stmt)
  1336.               || (ntype == del_stmt)
  1337.               || (ntype == pass_stmt)
  1338.               || (ntype == flow_stmt)
  1339.               || (ntype == import_stmt)
  1340.               || (ntype == global_stmt)
  1341.               || (ntype == assert_stmt)
  1342.               || (ntype == exec_stmt))
  1343.             res = validate_node(CHILD(tree, 0));
  1344.         else {
  1345.             res = 0;
  1346.             err_string("illegal small_stmt child type");
  1347.         }
  1348.     }
  1349.     else if (nch == 1) {
  1350.         res = 0;
  1351.         PyErr_Format(parser_error,
  1352.                      "Unrecognized child node of small_stmt: %d.",
  1353.                      TYPE(CHILD(tree, 0)));
  1354.     }
  1355.     return (res);
  1356. }
  1357.  
  1358.  
  1359. /*  compound_stmt:
  1360.  *      if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef
  1361.  */
  1362. static int
  1363. validate_compound_stmt(node *tree)
  1364. {
  1365.     int res = (validate_ntype(tree, compound_stmt)
  1366.                && validate_numnodes(tree, 1, "compound_stmt"));
  1367.     int ntype;
  1368.  
  1369.     if (!res)
  1370.         return (0);
  1371.  
  1372.     tree = CHILD(tree, 0);
  1373.     ntype = TYPE(tree);
  1374.     if (  (ntype == if_stmt)
  1375.           || (ntype == while_stmt)
  1376.           || (ntype == for_stmt)
  1377.           || (ntype == try_stmt)
  1378.           || (ntype == funcdef)
  1379.           || (ntype == classdef))
  1380.         res = validate_node(tree);
  1381.     else {
  1382.         res = 0;
  1383.         PyErr_Format(parser_error,
  1384.                      "Illegal compound statement type: %d.", TYPE(tree));
  1385.     }
  1386.     return (res);
  1387. }
  1388.  
  1389.  
  1390. static int
  1391. validate_expr_stmt(node *tree)
  1392. {
  1393.     int j;
  1394.     int nch = NCH(tree);
  1395.     int res = (validate_ntype(tree, expr_stmt)
  1396.                && is_odd(nch)
  1397.                && validate_testlist(CHILD(tree, 0)));
  1398.  
  1399.     if (res && nch == 3
  1400.         && TYPE(CHILD(tree, 1)) == augassign) {
  1401.         res = (validate_numnodes(CHILD(tree, 1), 1, "augassign")
  1402.                && validate_testlist(CHILD(tree, 2)));
  1403.  
  1404.         if (res) {
  1405.             char *s = STR(CHILD(CHILD(tree, 1), 0));
  1406.  
  1407.             res = (strcmp(s, "+=") == 0
  1408.                    || strcmp(s, "-=") == 0
  1409.                    || strcmp(s, "*=") == 0
  1410.                    || strcmp(s, "/=") == 0
  1411.                    || strcmp(s, "%=") == 0
  1412.                    || strcmp(s, "&=") == 0
  1413.                    || strcmp(s, "|=") == 0
  1414.                    || strcmp(s, "^=") == 0
  1415.                    || strcmp(s, "<<=") == 0
  1416.                    || strcmp(s, ">>=") == 0
  1417.                    || strcmp(s, "**=") == 0);
  1418.             if (!res)
  1419.                 err_string("illegal augmmented assignment operator");
  1420.         }
  1421.     }
  1422.     else {
  1423.         for (j = 1; res && (j < nch); j += 2)
  1424.             res = (validate_equal(CHILD(tree, j))
  1425.                    && validate_testlist(CHILD(tree, j + 1)));
  1426.     }
  1427.     return (res);
  1428. }
  1429.  
  1430.  
  1431. /*  print_stmt:
  1432.  *
  1433.  *      'print' ( [ test (',' test)* [','] ]
  1434.  *              | '>>' test [ (',' test)+ [','] ] )
  1435.  */
  1436. static int
  1437. validate_print_stmt(node *tree)
  1438. {
  1439.     int nch = NCH(tree);
  1440.     int res = (validate_ntype(tree, print_stmt)
  1441.                && (nch > 0)
  1442.                && validate_name(CHILD(tree, 0), "print"));
  1443.  
  1444.     if (res && nch > 1) {
  1445.         int sym = TYPE(CHILD(tree, 1));
  1446.         int i = 1;
  1447.         int allow_trailing_comma = 1;
  1448.  
  1449.         if (sym == test)
  1450.             res = validate_test(CHILD(tree, i++));
  1451.         else {
  1452.             if (nch < 3)
  1453.                 res = validate_numnodes(tree, 3, "print_stmt");
  1454.             else {
  1455.                 res = (validate_ntype(CHILD(tree, i), RIGHTSHIFT)
  1456.                        && validate_test(CHILD(tree, i+1)));
  1457.                 i += 2;
  1458.                 allow_trailing_comma = 0;
  1459.             }
  1460.         }
  1461.         if (res) {
  1462.             /*  ... (',' test)* [',']  */
  1463.             while (res && i+2 <= nch) {
  1464.                 res = (validate_comma(CHILD(tree, i))
  1465.                        && validate_test(CHILD(tree, i+1)));
  1466.                 allow_trailing_comma = 1;
  1467.                 i += 2;
  1468.             }
  1469.             if (res && !allow_trailing_comma)
  1470.                 res = validate_numnodes(tree, i, "print_stmt");
  1471.             else if (res && i < nch)
  1472.                 res = validate_comma(CHILD(tree, i));
  1473.         }
  1474.     }
  1475.     return (res);
  1476. }
  1477.  
  1478.  
  1479. static int
  1480. validate_del_stmt(node *tree)
  1481. {
  1482.     return (validate_numnodes(tree, 2, "del_stmt")
  1483.             && validate_name(CHILD(tree, 0), "del")
  1484.             && validate_exprlist(CHILD(tree, 1)));
  1485. }
  1486.  
  1487.  
  1488. static int
  1489. validate_return_stmt(node *tree)
  1490. {
  1491.     int nch = NCH(tree);
  1492.     int res = (validate_ntype(tree, return_stmt)
  1493.                && ((nch == 1) || (nch == 2))
  1494.                && validate_name(CHILD(tree, 0), "return"));
  1495.  
  1496.     if (res && (nch == 2))
  1497.         res = validate_testlist(CHILD(tree, 1));
  1498.  
  1499.     return (res);
  1500. }
  1501.  
  1502.  
  1503. static int
  1504. validate_raise_stmt(node *tree)
  1505. {
  1506.     int nch = NCH(tree);
  1507.     int res = (validate_ntype(tree, raise_stmt)
  1508.                && ((nch == 1) || (nch == 2) || (nch == 4) || (nch == 6)));
  1509.  
  1510.     if (res) {
  1511.         res = validate_name(CHILD(tree, 0), "raise");
  1512.         if (res && (nch >= 2))
  1513.             res = validate_test(CHILD(tree, 1));
  1514.         if (res && nch > 2) {
  1515.             res = (validate_comma(CHILD(tree, 2))
  1516.                    && validate_test(CHILD(tree, 3)));
  1517.             if (res && (nch > 4))
  1518.                 res = (validate_comma(CHILD(tree, 4))
  1519.                        && validate_test(CHILD(tree, 5)));
  1520.         }
  1521.     }
  1522.     else
  1523.         (void) validate_numnodes(tree, 2, "raise");
  1524.     if (res && (nch == 4))
  1525.         res = (validate_comma(CHILD(tree, 2))
  1526.                && validate_test(CHILD(tree, 3)));
  1527.  
  1528.     return (res);
  1529. }
  1530.  
  1531.  
  1532. static int
  1533. validate_import_as_name(node *tree)
  1534. {
  1535.     int nch = NCH(tree);
  1536.     int ok = validate_ntype(tree, import_as_name);
  1537.  
  1538.     if (ok) {
  1539.         if (nch == 1)
  1540.             ok = validate_name(CHILD(tree, 0), NULL);
  1541.         else if (nch == 3)
  1542.             ok = (validate_name(CHILD(tree, 0), NULL)
  1543.                   && validate_name(CHILD(tree, 1), "as")
  1544.                   && validate_name(CHILD(tree, 2), NULL));
  1545.         else
  1546.             ok = validate_numnodes(tree, 3, "import_as_name");
  1547.     }
  1548.     return ok;
  1549. }
  1550.  
  1551.  
  1552. /* dotted_as_name:  dotted_name [NAME NAME]
  1553.  */
  1554. static int
  1555. validate_dotted_as_name(node *tree)
  1556. {
  1557.     int nch = NCH(tree);
  1558.     int res = validate_ntype(tree, dotted_as_name);
  1559.  
  1560.     if (res) {
  1561.         if (nch == 1)
  1562.             res = validate_ntype(CHILD(tree, 0), dotted_name);
  1563.         else if (nch == 3)
  1564.             res = (validate_ntype(CHILD(tree, 0), dotted_name)
  1565.                    && validate_name(CHILD(tree, 1), "as")
  1566.                    && validate_name(CHILD(tree, 2), NULL));
  1567.         else {
  1568.             res = 0;
  1569.             err_string("Illegal number of children for dotted_as_name.");
  1570.         }
  1571.     }
  1572.     return res;
  1573. }
  1574.  
  1575.  
  1576. /*  import_stmt:
  1577.  *
  1578.  *    'import' dotted_as_name (',' dotted_as_name)*
  1579.  *  | 'from' dotted_name 'import' ('*' | import_as_name (',' import_as_name)*)
  1580.  */
  1581. static int
  1582. validate_import_stmt(node *tree)
  1583. {
  1584.     int nch = NCH(tree);
  1585.     int res = (validate_ntype(tree, import_stmt)
  1586.                && (nch >= 2) && is_even(nch)
  1587.                && validate_ntype(CHILD(tree, 0), NAME));
  1588.  
  1589.     if (res && (strcmp(STR(CHILD(tree, 0)), "import") == 0)) {
  1590.         int j;
  1591.  
  1592.         res = validate_dotted_as_name(CHILD(tree, 1));
  1593.         for (j = 2; res && (j < nch); j += 2)
  1594.             res = (validate_comma(CHILD(tree, j))
  1595.                    && validate_ntype(CHILD(tree, j + 1), dotted_name));
  1596.     }
  1597.     else if (res && (res = validate_name(CHILD(tree, 0), "from"))) {
  1598.         res = ((nch >= 4) && is_even(nch)
  1599.                && validate_name(CHILD(tree, 2), "import")
  1600.                && validate_dotted_as_name(CHILD(tree, 1)));
  1601.         if (nch == 4) {
  1602.             if (TYPE(CHILD(tree, 3)) == import_as_name)
  1603.                 res = validate_import_as_name(CHILD(tree, 3));
  1604.             else
  1605.                 res = validate_star(CHILD(tree, 3));
  1606.         }
  1607.         else {
  1608.             /*  'from' dotted_name 'import' import_as_name
  1609.              *      (',' import_as_name)+
  1610.              */
  1611.             int j;
  1612.             res = validate_import_as_name(CHILD(tree, 3));
  1613.             for (j = 4; res && (j < nch); j += 2)
  1614.                 res = (validate_comma(CHILD(tree, j))
  1615.                        && validate_import_as_name(CHILD(tree, j + 1)));
  1616.         }
  1617.     }
  1618.     else
  1619.         res = 0;
  1620.  
  1621.     return (res);
  1622. }
  1623.  
  1624.  
  1625. static int
  1626. validate_global_stmt(node *tree)
  1627. {
  1628.     int j;
  1629.     int nch = NCH(tree);
  1630.     int res = (validate_ntype(tree, global_stmt)
  1631.                && is_even(nch) && (nch >= 2));
  1632.  
  1633.     if (res)
  1634.         res = (validate_name(CHILD(tree, 0), "global")
  1635.                && validate_ntype(CHILD(tree, 1), NAME));
  1636.     for (j = 2; res && (j < nch); j += 2)
  1637.         res = (validate_comma(CHILD(tree, j))
  1638.                && validate_ntype(CHILD(tree, j + 1), NAME));
  1639.  
  1640.     return (res);
  1641. }
  1642.  
  1643.  
  1644. /*  exec_stmt:
  1645.  *
  1646.  *  'exec' expr ['in' test [',' test]]
  1647.  */
  1648. static int
  1649. validate_exec_stmt(node *tree)
  1650. {
  1651.     int nch = NCH(tree);
  1652.     int res = (validate_ntype(tree, exec_stmt)
  1653.                && ((nch == 2) || (nch == 4) || (nch == 6))
  1654.                && validate_name(CHILD(tree, 0), "exec")
  1655.                && validate_expr(CHILD(tree, 1)));
  1656.  
  1657.     if (!res && !PyErr_Occurred())
  1658.         err_string("Illegal exec statement.");
  1659.     if (res && (nch > 2))
  1660.         res = (validate_name(CHILD(tree, 2), "in")
  1661.                && validate_test(CHILD(tree, 3)));
  1662.     if (res && (nch == 6))
  1663.         res = (validate_comma(CHILD(tree, 4))
  1664.                && validate_test(CHILD(tree, 5)));
  1665.  
  1666.     return (res);
  1667. }
  1668.  
  1669.  
  1670. /*  assert_stmt:
  1671.  *
  1672.  *  'assert' test [',' test]
  1673.  */
  1674. static int
  1675. validate_assert_stmt(node *tree)
  1676. {
  1677.     int nch = NCH(tree);
  1678.     int res = (validate_ntype(tree, assert_stmt)
  1679.                && ((nch == 2) || (nch == 4))
  1680.                && (validate_name(CHILD(tree, 0), "__assert__") ||
  1681.                    validate_name(CHILD(tree, 0), "assert"))
  1682.                && validate_test(CHILD(tree, 1)));
  1683.  
  1684.     if (!res && !PyErr_Occurred())
  1685.         err_string("Illegal assert statement.");
  1686.     if (res && (nch > 2))
  1687.         res = (validate_comma(CHILD(tree, 2))
  1688.                && validate_test(CHILD(tree, 3)));
  1689.  
  1690.     return (res);
  1691. }
  1692.  
  1693.  
  1694. static int
  1695. validate_while(node *tree)
  1696. {
  1697.     int nch = NCH(tree);
  1698.     int res = (validate_ntype(tree, while_stmt)
  1699.                && ((nch == 4) || (nch == 7))
  1700.                && validate_name(CHILD(tree, 0), "while")
  1701.                && validate_test(CHILD(tree, 1))
  1702.                && validate_colon(CHILD(tree, 2))
  1703.                && validate_suite(CHILD(tree, 3)));
  1704.  
  1705.     if (res && (nch == 7))
  1706.         res = (validate_name(CHILD(tree, 4), "else")
  1707.                && validate_colon(CHILD(tree, 5))
  1708.                && validate_suite(CHILD(tree, 6)));
  1709.  
  1710.     return (res);
  1711. }
  1712.  
  1713.  
  1714. static int
  1715. validate_for(node *tree)
  1716. {
  1717.     int nch = NCH(tree);
  1718.     int res = (validate_ntype(tree, for_stmt)
  1719.                && ((nch == 6) || (nch == 9))
  1720.                && validate_name(CHILD(tree, 0), "for")
  1721.                && validate_exprlist(CHILD(tree, 1))
  1722.                && validate_name(CHILD(tree, 2), "in")
  1723.                && validate_testlist(CHILD(tree, 3))
  1724.                && validate_colon(CHILD(tree, 4))
  1725.                && validate_suite(CHILD(tree, 5)));
  1726.  
  1727.     if (res && (nch == 9))
  1728.         res = (validate_name(CHILD(tree, 6), "else")
  1729.                && validate_colon(CHILD(tree, 7))
  1730.                && validate_suite(CHILD(tree, 8)));
  1731.  
  1732.     return (res);
  1733. }
  1734.  
  1735.  
  1736. /*  try_stmt:
  1737.  *      'try' ':' suite (except_clause ':' suite)+ ['else' ':' suite]
  1738.  *    | 'try' ':' suite 'finally' ':' suite
  1739.  *
  1740.  */
  1741. static int
  1742. validate_try(node *tree)
  1743. {
  1744.     int nch = NCH(tree);
  1745.     int pos = 3;
  1746.     int res = (validate_ntype(tree, try_stmt)
  1747.                && (nch >= 6) && ((nch % 3) == 0));
  1748.  
  1749.     if (res)
  1750.         res = (validate_name(CHILD(tree, 0), "try")
  1751.                && validate_colon(CHILD(tree, 1))
  1752.                && validate_suite(CHILD(tree, 2))
  1753.                && validate_colon(CHILD(tree, nch - 2))
  1754.                && validate_suite(CHILD(tree, nch - 1)));
  1755.     else if (!PyErr_Occurred()) {
  1756.         const char* name = "except";
  1757.         if (TYPE(CHILD(tree, nch - 3)) != except_clause)
  1758.             name = STR(CHILD(tree, nch - 3));
  1759.  
  1760.         PyErr_Format(parser_error,
  1761.                      "Illegal number of children for try/%s node.", name);
  1762.     }
  1763.     /*  Skip past except_clause sections:  */
  1764.     while (res && (TYPE(CHILD(tree, pos)) == except_clause)) {
  1765.         res = (validate_except_clause(CHILD(tree, pos))
  1766.                && validate_colon(CHILD(tree, pos + 1))
  1767.                && validate_suite(CHILD(tree, pos + 2)));
  1768.         pos += 3;
  1769.     }
  1770.     if (res && (pos < nch)) {
  1771.         res = validate_ntype(CHILD(tree, pos), NAME);
  1772.         if (res && (strcmp(STR(CHILD(tree, pos)), "finally") == 0))
  1773.             res = (validate_numnodes(tree, 6, "try/finally")
  1774.                    && validate_colon(CHILD(tree, 4))
  1775.                    && validate_suite(CHILD(tree, 5)));
  1776.         else if (res) {
  1777.             if (nch == (pos + 3)) {
  1778.                 res = ((strcmp(STR(CHILD(tree, pos)), "except") == 0)
  1779.                        || (strcmp(STR(CHILD(tree, pos)), "else") == 0));
  1780.                 if (!res)
  1781.                     err_string("Illegal trailing triple in try statement.");
  1782.             }
  1783.             else if (nch == (pos + 6)) {
  1784.                 res = (validate_name(CHILD(tree, pos), "except")
  1785.                        && validate_colon(CHILD(tree, pos + 1))
  1786.                        && validate_suite(CHILD(tree, pos + 2))
  1787.                        && validate_name(CHILD(tree, pos + 3), "else"));
  1788.             }
  1789.             else
  1790.                 res = validate_numnodes(tree, pos + 3, "try/except");
  1791.         }
  1792.     }
  1793.     return (res);
  1794. }
  1795.  
  1796.  
  1797. static int
  1798. validate_except_clause(node *tree)
  1799. {
  1800.     int nch = NCH(tree);
  1801.     int res = (validate_ntype(tree, except_clause)
  1802.                && ((nch == 1) || (nch == 2) || (nch == 4))
  1803.                && validate_name(CHILD(tree, 0), "except"));
  1804.  
  1805.     if (res && (nch > 1))
  1806.         res = validate_test(CHILD(tree, 1));
  1807.     if (res && (nch == 4))
  1808.         res = (validate_comma(CHILD(tree, 2))
  1809.                && validate_test(CHILD(tree, 3)));
  1810.  
  1811.     return (res);
  1812. }
  1813.  
  1814.  
  1815. static int
  1816. validate_test(node *tree)
  1817. {
  1818.     int nch = NCH(tree);
  1819.     int res = validate_ntype(tree, test) && is_odd(nch);
  1820.  
  1821.     if (res && (TYPE(CHILD(tree, 0)) == lambdef))
  1822.         res = ((nch == 1)
  1823.                && validate_lambdef(CHILD(tree, 0)));
  1824.     else if (res) {
  1825.         int pos;
  1826.         res = validate_and_test(CHILD(tree, 0));
  1827.         for (pos = 1; res && (pos < nch); pos += 2)
  1828.             res = (validate_name(CHILD(tree, pos), "or")
  1829.                    && validate_and_test(CHILD(tree, pos + 1)));
  1830.     }
  1831.     return (res);
  1832. }
  1833.  
  1834.  
  1835. static int
  1836. validate_and_test(node *tree)
  1837. {
  1838.     int pos;
  1839.     int nch = NCH(tree);
  1840.     int res = (validate_ntype(tree, and_test)
  1841.                && is_odd(nch)
  1842.                && validate_not_test(CHILD(tree, 0)));
  1843.  
  1844.     for (pos = 1; res && (pos < nch); pos += 2)
  1845.         res = (validate_name(CHILD(tree, pos), "and")
  1846.                && validate_not_test(CHILD(tree, 0)));
  1847.  
  1848.     return (res);
  1849. }
  1850.  
  1851.  
  1852. static int
  1853. validate_not_test(node *tree)
  1854. {
  1855.     int nch = NCH(tree);
  1856.     int res = validate_ntype(tree, not_test) && ((nch == 1) || (nch == 2));
  1857.  
  1858.     if (res) {
  1859.         if (nch == 2)
  1860.             res = (validate_name(CHILD(tree, 0), "not")
  1861.                    && validate_not_test(CHILD(tree, 1)));
  1862.         else if (nch == 1)
  1863.             res = validate_comparison(CHILD(tree, 0));
  1864.     }
  1865.     return (res);
  1866. }
  1867.  
  1868.  
  1869. static int
  1870. validate_comparison(node *tree)
  1871. {
  1872.     int pos;
  1873.     int nch = NCH(tree);
  1874.     int res = (validate_ntype(tree, comparison)
  1875.                && is_odd(nch)
  1876.                && validate_expr(CHILD(tree, 0)));
  1877.  
  1878.     for (pos = 1; res && (pos < nch); pos += 2)
  1879.         res = (validate_comp_op(CHILD(tree, pos))
  1880.                && validate_expr(CHILD(tree, pos + 1)));
  1881.  
  1882.     return (res);
  1883. }
  1884.  
  1885.  
  1886. static int
  1887. validate_comp_op(node *tree)
  1888. {
  1889.     int res = 0;
  1890.     int nch = NCH(tree);
  1891.  
  1892.     if (!validate_ntype(tree, comp_op))
  1893.         return (0);
  1894.     if (nch == 1) {
  1895.         /*
  1896.          *  Only child will be a terminal with a well-defined symbolic name
  1897.          *  or a NAME with a string of either 'is' or 'in'
  1898.          */
  1899.         tree = CHILD(tree, 0);
  1900.         switch (TYPE(tree)) {
  1901.             case LESS:
  1902.             case GREATER:
  1903.             case EQEQUAL:
  1904.             case EQUAL:
  1905.             case LESSEQUAL:
  1906.             case GREATEREQUAL:
  1907.             case NOTEQUAL:
  1908.               res = 1;
  1909.               break;
  1910.             case NAME:
  1911.               res = ((strcmp(STR(tree), "in") == 0)
  1912.                      || (strcmp(STR(tree), "is") == 0));
  1913.               if (!res) {
  1914.                   PyErr_Format(parser_error,
  1915.                                "Illegal operator: '%s'.", STR(tree));
  1916.               }
  1917.               break;
  1918.           default:
  1919.               err_string("Illegal comparison operator type.");
  1920.               break;
  1921.         }
  1922.     }
  1923.     else if ((res = validate_numnodes(tree, 2, "comp_op")) != 0) {
  1924.         res = (validate_ntype(CHILD(tree, 0), NAME)
  1925.                && validate_ntype(CHILD(tree, 1), NAME)
  1926.                && (((strcmp(STR(CHILD(tree, 0)), "is") == 0)
  1927.                     && (strcmp(STR(CHILD(tree, 1)), "not") == 0))
  1928.                    || ((strcmp(STR(CHILD(tree, 0)), "not") == 0)
  1929.                        && (strcmp(STR(CHILD(tree, 1)), "in") == 0))));
  1930.         if (!res && !PyErr_Occurred())
  1931.             err_string("Unknown comparison operator.");
  1932.     }
  1933.     return (res);
  1934. }
  1935.  
  1936.  
  1937. static int
  1938. validate_expr(node *tree)
  1939. {
  1940.     int j;
  1941.     int nch = NCH(tree);
  1942.     int res = (validate_ntype(tree, expr)
  1943.                && is_odd(nch)
  1944.                && validate_xor_expr(CHILD(tree, 0)));
  1945.  
  1946.     for (j = 2; res && (j < nch); j += 2)
  1947.         res = (validate_xor_expr(CHILD(tree, j))
  1948.                && validate_vbar(CHILD(tree, j - 1)));
  1949.  
  1950.     return (res);
  1951. }
  1952.  
  1953.  
  1954. static int
  1955. validate_xor_expr(node *tree)
  1956. {
  1957.     int j;
  1958.     int nch = NCH(tree);
  1959.     int res = (validate_ntype(tree, xor_expr)
  1960.                && is_odd(nch)
  1961.                && validate_and_expr(CHILD(tree, 0)));
  1962.  
  1963.     for (j = 2; res && (j < nch); j += 2)
  1964.         res = (validate_circumflex(CHILD(tree, j - 1))
  1965.                && validate_and_expr(CHILD(tree, j)));
  1966.  
  1967.     return (res);
  1968. }
  1969.  
  1970.  
  1971. static int
  1972. validate_and_expr(node *tree)
  1973. {
  1974.     int pos;
  1975.     int nch = NCH(tree);
  1976.     int res = (validate_ntype(tree, and_expr)
  1977.                && is_odd(nch)
  1978.                && validate_shift_expr(CHILD(tree, 0)));
  1979.  
  1980.     for (pos = 1; res && (pos < nch); pos += 2)
  1981.         res = (validate_ampersand(CHILD(tree, pos))
  1982.                && validate_shift_expr(CHILD(tree, pos + 1)));
  1983.  
  1984.     return (res);
  1985. }
  1986.  
  1987.  
  1988. static int
  1989. validate_chain_two_ops(node *tree, int (*termvalid)(node *), int op1, int op2)
  1990.  {
  1991.     int pos = 1;
  1992.     int nch = NCH(tree);
  1993.     int res = (is_odd(nch)
  1994.                && (*termvalid)(CHILD(tree, 0)));
  1995.  
  1996.     for ( ; res && (pos < nch); pos += 2) {
  1997.         if (TYPE(CHILD(tree, pos)) != op1)
  1998.             res = validate_ntype(CHILD(tree, pos), op2);
  1999.         if (res)
  2000.             res = (*termvalid)(CHILD(tree, pos + 1));
  2001.     }
  2002.     return (res);
  2003. }
  2004.  
  2005.  
  2006. static int
  2007. validate_shift_expr(node *tree)
  2008. {
  2009.     return (validate_ntype(tree, shift_expr)
  2010.             && validate_chain_two_ops(tree, validate_arith_expr,
  2011.                                       LEFTSHIFT, RIGHTSHIFT));
  2012. }
  2013.  
  2014.  
  2015. static int
  2016. validate_arith_expr(node *tree)
  2017. {
  2018.     return (validate_ntype(tree, arith_expr)
  2019.             && validate_chain_two_ops(tree, validate_term, PLUS, MINUS));
  2020. }
  2021.  
  2022.  
  2023. static int
  2024. validate_term(node *tree)
  2025. {
  2026.     int pos = 1;
  2027.     int nch = NCH(tree);
  2028.     int res = (validate_ntype(tree, term)
  2029.                && is_odd(nch)
  2030.                && validate_factor(CHILD(tree, 0)));
  2031.  
  2032.     for ( ; res && (pos < nch); pos += 2)
  2033.         res = (((TYPE(CHILD(tree, pos)) == STAR)
  2034.                || (TYPE(CHILD(tree, pos)) == SLASH)
  2035.                || (TYPE(CHILD(tree, pos)) == PERCENT))
  2036.                && validate_factor(CHILD(tree, pos + 1)));
  2037.  
  2038.     return (res);
  2039. }
  2040.  
  2041.  
  2042. /*  factor:
  2043.  *
  2044.  *  factor: ('+'|'-'|'~') factor | power
  2045.  */
  2046. static int
  2047. validate_factor(node *tree)
  2048. {
  2049.     int nch = NCH(tree);
  2050.     int res = (validate_ntype(tree, factor)
  2051.                && (((nch == 2)
  2052.                     && ((TYPE(CHILD(tree, 0)) == PLUS)
  2053.                         || (TYPE(CHILD(tree, 0)) == MINUS)
  2054.                         || (TYPE(CHILD(tree, 0)) == TILDE))
  2055.                     && validate_factor(CHILD(tree, 1)))
  2056.                    || ((nch == 1)
  2057.                        && validate_power(CHILD(tree, 0)))));
  2058.     return (res);
  2059. }
  2060.  
  2061.  
  2062. /*  power:
  2063.  *
  2064.  *  power: atom trailer* ('**' factor)*
  2065.  */
  2066. static int
  2067. validate_power(node *tree)
  2068. {
  2069.     int pos = 1;
  2070.     int nch = NCH(tree);
  2071.     int res = (validate_ntype(tree, power) && (nch >= 1)
  2072.                && validate_atom(CHILD(tree, 0)));
  2073.  
  2074.     while (res && (pos < nch) && (TYPE(CHILD(tree, pos)) == trailer))
  2075.         res = validate_trailer(CHILD(tree, pos++));
  2076.     if (res && (pos < nch)) {
  2077.         if (!is_even(nch - pos)) {
  2078.             err_string("Illegal number of nodes for 'power'.");
  2079.             return (0);
  2080.         }
  2081.         for ( ; res && (pos < (nch - 1)); pos += 2)
  2082.             res = (validate_doublestar(CHILD(tree, pos))
  2083.                    && validate_factor(CHILD(tree, pos + 1)));
  2084.     }
  2085.     return (res);
  2086. }
  2087.  
  2088.  
  2089. static int
  2090. validate_atom(node *tree)
  2091. {
  2092.     int pos;
  2093.     int nch = NCH(tree);
  2094.     int res = validate_ntype(tree, atom);
  2095.  
  2096.     if (res && nch < 1)
  2097.         res = validate_numnodes(tree, nch+1, "atom");
  2098.     if (res) {
  2099.         switch (TYPE(CHILD(tree, 0))) {
  2100.           case LPAR:
  2101.             res = ((nch <= 3)
  2102.                    && (validate_rparen(CHILD(tree, nch - 1))));
  2103.  
  2104.             if (res && (nch == 3))
  2105.                 res = validate_testlist(CHILD(tree, 1));
  2106.             break;
  2107.           case LSQB:
  2108.             if (nch == 2)
  2109.                 res = validate_ntype(CHILD(tree, 1), RSQB);
  2110.             else if (nch == 3)
  2111.                 res = (validate_listmaker(CHILD(tree, 1))
  2112.                        && validate_ntype(CHILD(tree, 2), RSQB));
  2113.             else {
  2114.                 res = 0;
  2115.                 err_string("illegal list display atom");
  2116.             }
  2117.             break;
  2118.           case LBRACE:
  2119.             res = ((nch <= 3)
  2120.                    && validate_ntype(CHILD(tree, nch - 1), RBRACE));
  2121.  
  2122.             if (res && (nch == 3))
  2123.                 res = validate_dictmaker(CHILD(tree, 1));
  2124.             break;
  2125.           case BACKQUOTE:
  2126.             res = ((nch == 3)
  2127.                    && validate_testlist(CHILD(tree, 1))
  2128.                    && validate_ntype(CHILD(tree, 2), BACKQUOTE));
  2129.             break;
  2130.           case NAME:
  2131.           case NUMBER:
  2132.             res = (nch == 1);
  2133.             break;
  2134.           case STRING:
  2135.             for (pos = 1; res && (pos < nch); ++pos)
  2136.                 res = validate_ntype(CHILD(tree, pos), STRING);
  2137.             break;
  2138.           default:
  2139.             res = 0;
  2140.             break;
  2141.         }
  2142.     }
  2143.     return (res);
  2144. }
  2145.  
  2146.  
  2147. /*  listmaker:
  2148.  *    test ( list_for | (',' test)* [','] )
  2149.  */
  2150. static int
  2151. validate_listmaker(node *tree)
  2152. {
  2153.     int nch = NCH(tree);
  2154.     int ok = nch;
  2155.  
  2156.     if (nch == 0)
  2157.         err_string("missing child nodes of listmaker");
  2158.     else
  2159.         ok = validate_test(CHILD(tree, 0));
  2160.  
  2161.     /*
  2162.      *  list_iter | (',' test)* [',']
  2163.      */
  2164.     if (nch == 2 && TYPE(CHILD(tree, 1)) == list_for)
  2165.         ok = validate_list_for(CHILD(tree, 1));
  2166.     else {
  2167.         /*  (',' test)* [',']  */
  2168.         int i = 1;
  2169.         while (ok && nch - i >= 2) {
  2170.             ok = (validate_comma(CHILD(tree, i))
  2171.                   && validate_test(CHILD(tree, i+1)));
  2172.             i += 2;
  2173.         }
  2174.         if (ok && i == nch-1)
  2175.             ok = validate_comma(CHILD(tree, i));
  2176.         else if (i != nch) {
  2177.             ok = 0;
  2178.             err_string("illegal trailing nodes for listmaker");
  2179.         }
  2180.     }
  2181.     return ok;
  2182. }
  2183.  
  2184.  
  2185. /*  funcdef:
  2186.  *      'def' NAME parameters ':' suite
  2187.  *
  2188.  */
  2189. static int
  2190. validate_funcdef(node *tree)
  2191. {
  2192.     return (validate_ntype(tree, funcdef)
  2193.             && validate_numnodes(tree, 5, "funcdef")
  2194.             && validate_name(CHILD(tree, 0), "def")
  2195.             && validate_ntype(CHILD(tree, 1), NAME)
  2196.             && validate_colon(CHILD(tree, 3))
  2197.             && validate_parameters(CHILD(tree, 2))
  2198.             && validate_suite(CHILD(tree, 4)));
  2199. }
  2200.  
  2201.  
  2202. static int
  2203. validate_lambdef(node *tree)
  2204. {
  2205.     int nch = NCH(tree);
  2206.     int res = (validate_ntype(tree, lambdef)
  2207.                && ((nch == 3) || (nch == 4))
  2208.                && validate_name(CHILD(tree, 0), "lambda")
  2209.                && validate_colon(CHILD(tree, nch - 2))
  2210.                && validate_test(CHILD(tree, nch - 1)));
  2211.  
  2212.     if (res && (nch == 4))
  2213.         res = validate_varargslist(CHILD(tree, 1));
  2214.     else if (!res && !PyErr_Occurred())
  2215.         (void) validate_numnodes(tree, 3, "lambdef");
  2216.  
  2217.     return (res);
  2218. }
  2219.  
  2220.  
  2221. /*  arglist:
  2222.  *
  2223.  *  (argument ',')* (argument [','] | '*' test [',' '**' test] | '**' test)
  2224.  */
  2225. static int
  2226. validate_arglist(node *tree)
  2227. {
  2228.     int nch = NCH(tree);
  2229.     int i = 0;
  2230.     int ok = 1;
  2231.  
  2232.     if (nch <= 0)
  2233.         /* raise the right error from having an invalid number of children */
  2234.         return validate_numnodes(tree, nch + 1, "arglist");
  2235.  
  2236.     while (ok && nch-i >= 2) {
  2237.         /* skip leading (argument ',') */
  2238.         ok = (validate_argument(CHILD(tree, i))
  2239.               && validate_comma(CHILD(tree, i+1)));
  2240.         if (ok)
  2241.             i += 2;
  2242.         else
  2243.             PyErr_Clear();
  2244.     }
  2245.     ok = 1;
  2246.     if (nch-i > 0) {
  2247.         /*
  2248.          * argument | '*' test [',' '**' test] | '**' test
  2249.          */
  2250.         int sym = TYPE(CHILD(tree, i));
  2251.  
  2252.         if (sym == argument) {
  2253.             ok = validate_argument(CHILD(tree, i));
  2254.             if (ok && i+1 != nch) {
  2255.                 err_string("illegal arglist specification"
  2256.                            " (extra stuff on end)");
  2257.                 ok = 0;
  2258.             }
  2259.         }
  2260.         else if (sym == STAR) {
  2261.             ok = validate_star(CHILD(tree, i));
  2262.             if (ok && (nch-i == 2))
  2263.                 ok = validate_test(CHILD(tree, i+1));
  2264.             else if (ok && (nch-i == 5))
  2265.                 ok = (validate_test(CHILD(tree, i+1))
  2266.                       && validate_comma(CHILD(tree, i+2))
  2267.                       && validate_doublestar(CHILD(tree, i+3))
  2268.                       && validate_test(CHILD(tree, i+4)));
  2269.             else {
  2270.                 err_string("illegal use of '*' in arglist");
  2271.                 ok = 0;
  2272.             }
  2273.         }
  2274.         else if (sym == DOUBLESTAR) {
  2275.             if (nch-i == 2)
  2276.                 ok = (validate_doublestar(CHILD(tree, i))
  2277.                       && validate_test(CHILD(tree, i+1)));
  2278.             else {
  2279.                 err_string("illegal use of '**' in arglist");
  2280.                 ok = 0;
  2281.             }
  2282.         }
  2283.         else {
  2284.             err_string("illegal arglist specification");
  2285.             ok = 0;
  2286.         }
  2287.     }
  2288.     return (ok);
  2289. }
  2290.  
  2291.  
  2292.  
  2293. /*  argument:
  2294.  *
  2295.  *  [test '='] test
  2296.  */
  2297. static int
  2298. validate_argument(node *tree)
  2299. {
  2300.     int nch = NCH(tree);
  2301.     int res = (validate_ntype(tree, argument)
  2302.                && ((nch == 1) || (nch == 3))
  2303.                && validate_test(CHILD(tree, 0)));
  2304.  
  2305.     if (res && (nch == 3))
  2306.         res = (validate_equal(CHILD(tree, 1))
  2307.                && validate_test(CHILD(tree, 2)));
  2308.  
  2309.     return (res);
  2310. }
  2311.  
  2312.  
  2313.  
  2314. /*  trailer:
  2315.  *
  2316.  *  '(' [arglist] ')' | '[' subscriptlist ']' | '.' NAME
  2317.  */
  2318. static int
  2319. validate_trailer(node *tree)
  2320. {
  2321.     int nch = NCH(tree);
  2322.     int res = validate_ntype(tree, trailer) && ((nch == 2) || (nch == 3));
  2323.  
  2324.     if (res) {
  2325.         switch (TYPE(CHILD(tree, 0))) {
  2326.           case LPAR:
  2327.             res = validate_rparen(CHILD(tree, nch - 1));
  2328.             if (res && (nch == 3))
  2329.                 res = validate_arglist(CHILD(tree, 1));
  2330.             break;
  2331.           case LSQB:
  2332.             res = (validate_numnodes(tree, 3, "trailer")
  2333.                    && validate_subscriptlist(CHILD(tree, 1))
  2334.                    && validate_ntype(CHILD(tree, 2), RSQB));
  2335.             break;
  2336.           case DOT:
  2337.             res = (validate_numnodes(tree, 2, "trailer")
  2338.                    && validate_ntype(CHILD(tree, 1), NAME));
  2339.             break;
  2340.           default:
  2341.             res = 0;
  2342.             break;
  2343.         }
  2344.     }
  2345.     else {
  2346.         (void) validate_numnodes(tree, 2, "trailer");
  2347.     }
  2348.     return (res);
  2349. }
  2350.  
  2351.  
  2352. /*  subscriptlist:
  2353.  *
  2354.  *  subscript (',' subscript)* [',']
  2355.  */
  2356. static int
  2357. validate_subscriptlist(node *tree)
  2358. {
  2359.     return (validate_repeating_list(tree, subscriptlist,
  2360.                                     validate_subscript, "subscriptlist"));
  2361. }
  2362.  
  2363.  
  2364. /*  subscript:
  2365.  *
  2366.  *  '.' '.' '.' | test | [test] ':' [test] [sliceop]
  2367.  */
  2368. static int
  2369. validate_subscript(node *tree)
  2370. {
  2371.     int offset = 0;
  2372.     int nch = NCH(tree);
  2373.     int res = validate_ntype(tree, subscript) && (nch >= 1) && (nch <= 4);
  2374.  
  2375.     if (!res) {
  2376.         if (!PyErr_Occurred())
  2377.             err_string("invalid number of arguments for subscript node");
  2378.         return (0);
  2379.     }
  2380.     if (TYPE(CHILD(tree, 0)) == DOT)
  2381.         /* take care of ('.' '.' '.') possibility */
  2382.         return (validate_numnodes(tree, 3, "subscript")
  2383.                 && validate_dot(CHILD(tree, 0))
  2384.                 && validate_dot(CHILD(tree, 1))
  2385.                 && validate_dot(CHILD(tree, 2)));
  2386.     if (nch == 1) {
  2387.         if (TYPE(CHILD(tree, 0)) == test)
  2388.             res = validate_test(CHILD(tree, 0));
  2389.         else
  2390.             res = validate_colon(CHILD(tree, 0));
  2391.         return (res);
  2392.     }
  2393.     /*  Must be [test] ':' [test] [sliceop],
  2394.      *  but at least one of the optional components will
  2395.      *  be present, but we don't know which yet.
  2396.      */
  2397.     if ((TYPE(CHILD(tree, 0)) != COLON) || (nch == 4)) {
  2398.         res = validate_test(CHILD(tree, 0));
  2399.         offset = 1;
  2400.     }
  2401.     if (res)
  2402.         res = validate_colon(CHILD(tree, offset));
  2403.     if (res) {
  2404.         int rem = nch - ++offset;
  2405.         if (rem) {
  2406.             if (TYPE(CHILD(tree, offset)) == test) {
  2407.                 res = validate_test(CHILD(tree, offset));
  2408.                 ++offset;
  2409.                 --rem;
  2410.             }
  2411.             if (res && rem)
  2412.                 res = validate_sliceop(CHILD(tree, offset));
  2413.         }
  2414.     }
  2415.     return (res);
  2416. }
  2417.  
  2418.  
  2419. static int
  2420. validate_sliceop(node *tree)
  2421. {
  2422.     int nch = NCH(tree);
  2423.     int res = ((nch == 1) || validate_numnodes(tree, 2, "sliceop"))
  2424.               && validate_ntype(tree, sliceop);
  2425.     if (!res && !PyErr_Occurred()) {
  2426.         res = validate_numnodes(tree, 1, "sliceop");
  2427.     }
  2428.     if (res)
  2429.         res = validate_colon(CHILD(tree, 0));
  2430.     if (res && (nch == 2))
  2431.         res = validate_test(CHILD(tree, 1));
  2432.  
  2433.     return (res);
  2434. }
  2435.  
  2436.  
  2437. static int
  2438. validate_exprlist(node *tree)
  2439. {
  2440.     return (validate_repeating_list(tree, exprlist,
  2441.                                     validate_expr, "exprlist"));
  2442. }
  2443.  
  2444.  
  2445. static int
  2446. validate_dictmaker(node *tree)
  2447. {
  2448.     int nch = NCH(tree);
  2449.     int res = (validate_ntype(tree, dictmaker)
  2450.                && (nch >= 3)
  2451.                && validate_test(CHILD(tree, 0))
  2452.                && validate_colon(CHILD(tree, 1))
  2453.                && validate_test(CHILD(tree, 2)));
  2454.  
  2455.     if (res && ((nch % 4) == 0))
  2456.         res = validate_comma(CHILD(tree, --nch));
  2457.     else if (res)
  2458.         res = ((nch % 4) == 3);
  2459.  
  2460.     if (res && (nch > 3)) {
  2461.         int pos = 3;
  2462.         /*  ( ',' test ':' test )*  */
  2463.         while (res && (pos < nch)) {
  2464.             res = (validate_comma(CHILD(tree, pos))
  2465.                    && validate_test(CHILD(tree, pos + 1))
  2466.                    && validate_colon(CHILD(tree, pos + 2))
  2467.                    && validate_test(CHILD(tree, pos + 3)));
  2468.             pos += 4;
  2469.         }
  2470.     }
  2471.     return (res);
  2472. }
  2473.  
  2474.  
  2475. static int
  2476. validate_eval_input(node *tree)
  2477. {
  2478.     int pos;
  2479.     int nch = NCH(tree);
  2480.     int res = (validate_ntype(tree, eval_input)
  2481.                && (nch >= 2)
  2482.                && validate_testlist(CHILD(tree, 0))
  2483.                && validate_ntype(CHILD(tree, nch - 1), ENDMARKER));
  2484.  
  2485.     for (pos = 1; res && (pos < (nch - 1)); ++pos)
  2486.         res = validate_ntype(CHILD(tree, pos), NEWLINE);
  2487.  
  2488.     return (res);
  2489. }
  2490.  
  2491.  
  2492. static int
  2493. validate_node(node *tree)
  2494. {
  2495.     int   nch  = 0;                     /* num. children on current node  */
  2496.     int   res  = 1;                     /* result value                   */
  2497.     node* next = 0;                     /* node to process after this one */
  2498.  
  2499.     while (res & (tree != 0)) {
  2500.         nch  = NCH(tree);
  2501.         next = 0;
  2502.         switch (TYPE(tree)) {
  2503.             /*
  2504.              *  Definition nodes.
  2505.              */
  2506.           case funcdef:
  2507.             res = validate_funcdef(tree);
  2508.             break;
  2509.           case classdef:
  2510.             res = validate_class(tree);
  2511.             break;
  2512.             /*
  2513.              *  "Trivial" parse tree nodes.
  2514.              *  (Why did I call these trivial?)
  2515.              */
  2516.           case stmt:
  2517.             res = validate_stmt(tree);
  2518.             break;
  2519.           case small_stmt:
  2520.             /*
  2521.              *  expr_stmt | print_stmt | del_stmt | pass_stmt | flow_stmt
  2522.              *  | import_stmt | global_stmt | exec_stmt | assert_stmt
  2523.              */
  2524.             res = validate_small_stmt(tree);
  2525.             break;
  2526.           case flow_stmt:
  2527.             res  = (validate_numnodes(tree, 1, "flow_stmt")
  2528.                     && ((TYPE(CHILD(tree, 0)) == break_stmt)
  2529.                         || (TYPE(CHILD(tree, 0)) == continue_stmt)
  2530.                         || (TYPE(CHILD(tree, 0)) == return_stmt)
  2531.                         || (TYPE(CHILD(tree, 0)) == raise_stmt)));
  2532.             if (res)
  2533.                 next = CHILD(tree, 0);
  2534.             else if (nch == 1)
  2535.                 err_string("Illegal flow_stmt type.");
  2536.             break;
  2537.             /*
  2538.              *  Compound statements.
  2539.              */
  2540.           case simple_stmt:
  2541.             res = validate_simple_stmt(tree);
  2542.             break;
  2543.           case compound_stmt:
  2544.             res = validate_compound_stmt(tree);
  2545.             break;
  2546.             /*
  2547.              *  Fundamental statements.
  2548.              */
  2549.           case expr_stmt:
  2550.             res = validate_expr_stmt(tree);
  2551.             break;
  2552.           case print_stmt:
  2553.             res = validate_print_stmt(tree);
  2554.             break;
  2555.           case del_stmt:
  2556.             res = validate_del_stmt(tree);
  2557.             break;
  2558.           case pass_stmt:
  2559.             res = (validate_numnodes(tree, 1, "pass")
  2560.                    && validate_name(CHILD(tree, 0), "pass"));
  2561.             break;
  2562.           case break_stmt:
  2563.             res = (validate_numnodes(tree, 1, "break")
  2564.                    && validate_name(CHILD(tree, 0), "break"));
  2565.             break;
  2566.           case continue_stmt:
  2567.             res = (validate_numnodes(tree, 1, "continue")
  2568.                    && validate_name(CHILD(tree, 0), "continue"));
  2569.             break;
  2570.           case return_stmt:
  2571.             res = validate_return_stmt(tree);
  2572.             break;
  2573.           case raise_stmt:
  2574.             res = validate_raise_stmt(tree);
  2575.             break;
  2576.           case import_stmt:
  2577.             res = validate_import_stmt(tree);
  2578.             break;
  2579.           case global_stmt:
  2580.             res = validate_global_stmt(tree);
  2581.             break;
  2582.           case exec_stmt:
  2583.             res = validate_exec_stmt(tree);
  2584.             break;
  2585.           case assert_stmt:
  2586.             res = validate_assert_stmt(tree);
  2587.             break;
  2588.           case if_stmt:
  2589.             res = validate_if(tree);
  2590.             break;
  2591.           case while_stmt:
  2592.             res = validate_while(tree);
  2593.             break;
  2594.           case for_stmt:
  2595.             res = validate_for(tree);
  2596.             break;
  2597.           case try_stmt:
  2598.             res = validate_try(tree);
  2599.             break;
  2600.           case suite:
  2601.             res = validate_suite(tree);
  2602.             break;
  2603.             /*
  2604.              *  Expression nodes.
  2605.              */
  2606.           case testlist:
  2607.             res = validate_testlist(tree);
  2608.             break;
  2609.           case test:
  2610.             res = validate_test(tree);
  2611.             break;
  2612.           case and_test:
  2613.             res = validate_and_test(tree);
  2614.             break;
  2615.           case not_test:
  2616.             res = validate_not_test(tree);
  2617.             break;
  2618.           case comparison:
  2619.             res = validate_comparison(tree);
  2620.             break;
  2621.           case exprlist:
  2622.             res = validate_exprlist(tree);
  2623.             break;
  2624.           case comp_op:
  2625.             res = validate_comp_op(tree);
  2626.             break;
  2627.           case expr:
  2628.             res = validate_expr(tree);
  2629.             break;
  2630.           case xor_expr:
  2631.             res = validate_xor_expr(tree);
  2632.             break;
  2633.           case and_expr:
  2634.             res = validate_and_expr(tree);
  2635.             break;
  2636.           case shift_expr:
  2637.             res = validate_shift_expr(tree);
  2638.             break;
  2639.           case arith_expr:
  2640.             res = validate_arith_expr(tree);
  2641.             break;
  2642.           case term:
  2643.             res = validate_term(tree);
  2644.             break;
  2645.           case factor:
  2646.             res = validate_factor(tree);
  2647.             break;
  2648.           case power:
  2649.             res = validate_power(tree);
  2650.             break;
  2651.           case atom:
  2652.             res = validate_atom(tree);
  2653.             break;
  2654.  
  2655.           default:
  2656.             /* Hopefully never reached! */
  2657.             err_string("Unrecogniged node type.");
  2658.             res = 0;
  2659.             break;
  2660.         }
  2661.         tree = next;
  2662.     }
  2663.     return (res);
  2664. }
  2665.  
  2666.  
  2667. static int
  2668. validate_expr_tree(node *tree)
  2669. {
  2670.     int res = validate_eval_input(tree);
  2671.  
  2672.     if (!res && !PyErr_Occurred())
  2673.         err_string("Could not validate expression tuple.");
  2674.  
  2675.     return (res);
  2676. }
  2677.  
  2678.  
  2679. /*  file_input:
  2680.  *      (NEWLINE | stmt)* ENDMARKER
  2681.  */
  2682. static int
  2683. validate_file_input(node *tree)
  2684. {
  2685.     int j   = 0;
  2686.     int nch = NCH(tree) - 1;
  2687.     int res = ((nch >= 0)
  2688.                && validate_ntype(CHILD(tree, nch), ENDMARKER));
  2689.  
  2690.     for ( ; res && (j < nch); ++j) {
  2691.         if (TYPE(CHILD(tree, j)) == stmt)
  2692.             res = validate_stmt(CHILD(tree, j));
  2693.         else
  2694.             res = validate_newline(CHILD(tree, j));
  2695.     }
  2696.     /*  This stays in to prevent any internal failures from getting to the
  2697.      *  user.  Hopefully, this won't be needed.  If a user reports getting
  2698.      *  this, we have some debugging to do.
  2699.      */
  2700.     if (!res && !PyErr_Occurred())
  2701.         err_string("VALIDATION FAILURE: report this to the maintainer!.");
  2702.  
  2703.     return (res);
  2704. }
  2705.  
  2706.  
  2707. static PyObject*
  2708. pickle_constructor = NULL;
  2709.  
  2710.  
  2711. static PyObject*
  2712. parser__pickler(PyObject *self, PyObject *args)
  2713. {
  2714.     NOTE(ARGUNUSED(self))
  2715.     PyObject *result = NULL;
  2716.     PyObject *ast = NULL;
  2717.     PyObject *empty_dict = NULL;
  2718.  
  2719.     if (PyArg_ParseTuple(args, "O!:_pickler", &PyAST_Type, &ast)) {
  2720.         PyObject *newargs;
  2721.         PyObject *tuple;
  2722.  
  2723.         if ((empty_dict = PyDict_New()) == NULL)
  2724.             goto finally;
  2725.         if ((newargs = Py_BuildValue("Oi", ast, 1)) == NULL)
  2726.             goto finally;
  2727.         tuple = parser_ast2tuple((PyAST_Object*)NULL, newargs, empty_dict);
  2728.         if (tuple != NULL) {
  2729.             result = Py_BuildValue("O(O)", pickle_constructor, tuple);
  2730.             Py_DECREF(tuple);
  2731.         }
  2732.         Py_DECREF(empty_dict);
  2733.         Py_DECREF(newargs);
  2734.     }
  2735.   finally:
  2736.     Py_XDECREF(empty_dict);
  2737.  
  2738.     return (result);
  2739. }
  2740.  
  2741.  
  2742. /*  Functions exported by this module.  Most of this should probably
  2743.  *  be converted into an AST object with methods, but that is better
  2744.  *  done directly in Python, allowing subclasses to be created directly.
  2745.  *  We'd really have to write a wrapper around it all anyway to allow
  2746.  *  inheritance.
  2747.  */
  2748. static PyMethodDef parser_functions[] =  {
  2749.     {"ast2tuple",       (PyCFunction)parser_ast2tuple,  PUBLIC_METHOD_TYPE,
  2750.         "Creates a tuple-tree representation of an AST."},
  2751.     {"ast2list",        (PyCFunction)parser_ast2list,   PUBLIC_METHOD_TYPE,
  2752.         "Creates a list-tree representation of an AST."},
  2753.     {"compileast",      (PyCFunction)parser_compileast, PUBLIC_METHOD_TYPE,
  2754.         "Compiles an AST object into a code object."},
  2755.     {"expr",            (PyCFunction)parser_expr,       PUBLIC_METHOD_TYPE,
  2756.         "Creates an AST object from an expression."},
  2757.     {"isexpr",          (PyCFunction)parser_isexpr,     PUBLIC_METHOD_TYPE,
  2758.         "Determines if an AST object was created from an expression."},
  2759.     {"issuite",         (PyCFunction)parser_issuite,    PUBLIC_METHOD_TYPE,
  2760.         "Determines if an AST object was created from a suite."},
  2761.     {"suite",           (PyCFunction)parser_suite,      PUBLIC_METHOD_TYPE,
  2762.         "Creates an AST object from a suite."},
  2763.     {"sequence2ast",    (PyCFunction)parser_tuple2ast,  PUBLIC_METHOD_TYPE,
  2764.         "Creates an AST object from a tree representation."},
  2765.     {"tuple2ast",       (PyCFunction)parser_tuple2ast,  PUBLIC_METHOD_TYPE,
  2766.         "Creates an AST object from a tree representation."},
  2767.  
  2768.     /* private stuff: support pickle module */
  2769.     {"_pickler",        (PyCFunction)parser__pickler,   METH_VARARGS,
  2770.         "Returns the pickle magic to allow ast objects to be pickled."},
  2771.  
  2772.     {NULL, NULL, 0, NULL}
  2773.     };
  2774.  
  2775.  
  2776. DL_EXPORT(void) initparser(void);  /* supply a prototype */
  2777.  
  2778. DL_EXPORT(void)
  2779. initparser(void)
  2780. {
  2781.     PyObject* module;
  2782.     PyObject* dict;
  2783.         
  2784.     PyAST_Type.ob_type = &PyType_Type;
  2785.     module = Py_InitModule("parser", parser_functions);
  2786.     dict = PyModule_GetDict(module);
  2787.  
  2788.     if (parser_error == 0)
  2789.         parser_error = PyErr_NewException("parser.ParserError", NULL, NULL);
  2790.  
  2791.     if ((parser_error == 0)
  2792.         || (PyDict_SetItemString(dict, "ParserError", parser_error) != 0))
  2793.     {
  2794.         /* caller will check PyErr_Occurred() */
  2795.         return;
  2796.     }
  2797.     /*
  2798.      *  Nice to have, but don't cry if we fail.
  2799.      */
  2800.     Py_INCREF(&PyAST_Type);
  2801.     PyDict_SetItemString(dict, "ASTType", (PyObject*)&PyAST_Type);
  2802.  
  2803.     PyDict_SetItemString(dict, "__copyright__",
  2804.                          PyString_FromString(parser_copyright_string));
  2805.     PyDict_SetItemString(dict, "__doc__",
  2806.                          PyString_FromString(parser_doc_string));
  2807.     PyDict_SetItemString(dict, "__version__",
  2808.                          PyString_FromString(parser_version_string));
  2809.  
  2810.     /* register to support pickling */
  2811.     module = PyImport_ImportModule("copy_reg");
  2812.     if (module != NULL) {
  2813.         PyObject *func, *pickler;
  2814.  
  2815.         func = PyObject_GetAttrString(module, "pickle");
  2816.         pickle_constructor = PyDict_GetItemString(dict, "sequence2ast");
  2817.         pickler = PyDict_GetItemString(dict, "_pickler");
  2818.         Py_XINCREF(pickle_constructor);
  2819.         if ((func != NULL) && (pickle_constructor != NULL)
  2820.             && (pickler != NULL)) {
  2821.             PyObject *res;
  2822.  
  2823.             res = PyObject_CallFunction(
  2824.                     func, "OOO", &PyAST_Type, pickler, pickle_constructor);
  2825.             Py_XDECREF(res);
  2826.         }
  2827.         Py_XDECREF(func);
  2828.         Py_DECREF(module);
  2829.     }
  2830. }
  2831.