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 "Python-ast.h"                 /* mod_ty */

    30 #include "graminit.h"                   /* symbols defined in the grammar */

    31 #include "node.h"                       /* internal parser structure      */

    32 #include "errcode.h"                    /* error codes for PyNode_*()     */

    33 #include "token.h"                      /* token definitions              */

    34 #include "grammar.h"

    35 #include "parsetok.h"

    36                                         /* ISTERMINAL() / ISNONTERMINAL() */

    37 #include "compile.h"

    38 #undef Yield

    39 #include "ast.h"

    40 #include "pyarena.h"

    41 

    42 extern grammar _PyParser_Grammar; /* From graminit.c */

    43 

    44 #ifdef lint

    45 #include <note.h>

    46 #else

    47 #define NOTE(x)

    48 #endif

    49 

    50 /*  String constants used to initialize module attributes.

    51  *

    52  */

    53 static char parser_copyright_string[] =

    54 "Copyright 1995-1996 by Virginia Polytechnic Institute & State\n\

    55 University, Blacksburg, Virginia, USA, and Fred L. Drake, Jr., Reston,\n\

    56 Virginia, USA.  Portions copyright 1991-1995 by Stichting Mathematisch\n\

    57 Centrum, Amsterdam, The Netherlands.";

    58 

    59 

    60 PyDoc_STRVAR(parser_doc_string,

    61 "This is an interface to Python's internal parser.");

    62 

    63 static char parser_version_string[] = "0.5";

    64 

    65 

    66 typedef PyObject* (*SeqMaker) (Py_ssize_t length);

    67 typedef int (*SeqInserter) (PyObject* sequence,

    68                             Py_ssize_t index,

    69                             PyObject* element);

    70 

    71 /*  The function below is copyrighted by Stichting Mathematisch Centrum.  The

    72  *  original copyright statement is included below, and continues to apply

    73  *  in full to the function immediately following.  All other material is

    74  *  original, copyrighted by Fred L. Drake, Jr. and Virginia Polytechnic

    75  *  Institute and State University.  Changes were made to comply with the

    76  *  new naming conventions.  Added arguments to provide support for creating

    77  *  lists as well as tuples, and optionally including the line numbers.

    78  */

    79 

    80 

    81 static PyObject*

    82 node2tuple(node *n,                     /* node to convert               */

    83            SeqMaker mkseq,              /* create sequence               */

    84            SeqInserter addelem,         /* func. to add elem. in seq.    */

    85            int lineno,                  /* include line numbers?         */

    86            int col_offset)              /* include column offsets?       */

    87 {

    88     if (n == NULL) {

    89         Py_INCREF(Py_None);

    90         return (Py_None);

    91     }

    92     if (ISNONTERMINAL(TYPE(n))) {

    93         int i;

    94         PyObject *v;

    95         PyObject *w;

    96 

    97         v = mkseq(1 + NCH(n) + (TYPE(n) == encoding_decl));

    98         if (v == NULL)

    99             return (v);

   100         w = PyInt_FromLong(TYPE(n));

   101         if (w == NULL) {

   102             Py_DECREF(v);

   103             return ((PyObject*) NULL);

   104         }

   105         (void) addelem(v, 0, w);

   106         for (i = 0; i < NCH(n); i++) {

   107             w = node2tuple(CHILD(n, i), mkseq, addelem, lineno, col_offset);

   108             if (w == NULL) {

   109                 Py_DECREF(v);

   110                 return ((PyObject*) NULL);

   111             }

   112             (void) addelem(v, i+1, w);

   113         }

   114 

   115         if (TYPE(n) == encoding_decl)

   116             (void) addelem(v, i+1, PyString_FromString(STR(n)));

   117         return (v);

   118     }

   119     else if (ISTERMINAL(TYPE(n))) {

   120         PyObject *result = mkseq(2 + lineno + col_offset);

   121         if (result != NULL) {

   122             (void) addelem(result, 0, PyInt_FromLong(TYPE(n)));

   123             (void) addelem(result, 1, PyString_FromString(STR(n)));

   124             if (lineno == 1)

   125                 (void) addelem(result, 2, PyInt_FromLong(n->n_lineno));

   126             if (col_offset == 1)

   127                 (void) addelem(result, 3, PyInt_FromLong(n->n_col_offset));

   128         }

   129         return (result);

   130     }

   131     else {

   132         PyErr_SetString(PyExc_SystemError,

   133                         "unrecognized parse tree node type");

   134         return ((PyObject*) NULL);

   135     }

   136 }

   137 /*

   138  *  End of material copyrighted by Stichting Mathematisch Centrum.

   139  */

   140 

   141 

   142 

   143 /*  There are two types of intermediate objects we're interested in:

   144  *  'eval' and 'exec' types.  These constants can be used in the st_type

   145  *  field of the object type to identify which any given object represents.

   146  *  These should probably go in an external header to allow other extensions

   147  *  to use them, but then, we really should be using C++ too.  ;-)

   148  */

   149 

   150 #define PyST_EXPR  1

   151 #define PyST_SUITE 2

   152 

   153 

   154 /*  These are the internal objects and definitions required to implement the

   155  *  ST type.  Most of the internal names are more reminiscent of the 'old'

   156  *  naming style, but the code uses the new naming convention.

   157  */

   158 

   159 static PyObject*

   160 parser_error = 0;

   161 

   162 

   163 typedef struct {

   164     PyObject_HEAD                       /* standard object header           */

   165     node* st_node;                      /* the node* returned by the parser */

   166     int   st_type;                      /* EXPR or SUITE ?                  */

   167     PyCompilerFlags st_flags;           /* Parser and compiler flags        */

   168 } PyST_Object;

   169 

   170 

   171 static void parser_free(PyST_Object *st);

   172 static int parser_compare(PyST_Object *left, PyST_Object *right);

   173 static PyObject *parser_getattr(PyObject *self, char *name);

   174 

   175 

   176 static

   177 PyTypeObject PyST_Type = {

   178     PyVarObject_HEAD_INIT(NULL, 0)

   179     "parser.st",                        /* tp_name              */

   180     (int) sizeof(PyST_Object),          /* tp_basicsize         */

   181     0,                                  /* tp_itemsize          */

   182     (destructor)parser_free,            /* tp_dealloc           */

   183     0,                                  /* tp_print             */

   184     parser_getattr,                     /* tp_getattr           */

   185     0,                                  /* tp_setattr           */

   186     (cmpfunc)parser_compare,            /* tp_compare           */

   187     0,                                  /* tp_repr              */

   188     0,                                  /* tp_as_number         */

   189     0,                                  /* tp_as_sequence       */

   190     0,                                  /* tp_as_mapping        */

   191     0,                                  /* tp_hash              */

   192     0,                                  /* tp_call              */

   193     0,                                  /* tp_str               */

   194     0,                                  /* tp_getattro          */

   195     0,                                  /* tp_setattro          */

   196 

   197     /* Functions to access object as input/output buffer */

   198     0,                                  /* tp_as_buffer         */

   199 

   200     Py_TPFLAGS_DEFAULT,                 /* tp_flags             */

   201 

   202     /* __doc__ */

   203     "Intermediate representation of a Python parse tree."

   204 };  /* PyST_Type */

   205 

   206 

   207 static int

   208 parser_compare_nodes(node *left, node *right)

   209 {

   210     int j;

   211 

   212     if (TYPE(left) < TYPE(right))

   213         return (-1);

   214 

   215     if (TYPE(right) < TYPE(left))

   216         return (1);

   217 

   218     if (ISTERMINAL(TYPE(left)))

   219         return (strcmp(STR(left), STR(right)));

   220 

   221     if (NCH(left) < NCH(right))

   222         return (-1);

   223 

   224     if (NCH(right) < NCH(left))

   225         return (1);

   226 

   227     for (j = 0; j < NCH(left); ++j) {

   228         int v = parser_compare_nodes(CHILD(left, j), CHILD(right, j));

   229 

   230         if (v != 0)

   231             return (v);

   232     }

   233     return (0);

   234 }

   235 

   236 

   237 /*  int parser_compare(PyST_Object* left, PyST_Object* right)

   238  *

   239  *  Comparison function used by the Python operators ==, !=, <, >, <=, >=

   240  *  This really just wraps a call to parser_compare_nodes() with some easy

   241  *  checks and protection code.

   242  *

   243  */

   244 static int

   245 parser_compare(PyST_Object *left, PyST_Object *right)

   246 {

   247     if (left == right)

   248         return (0);

   249 

   250     if ((left == 0) || (right == 0))

   251         return (-1);

   252 

   253     return (parser_compare_nodes(left->st_node, right->st_node));

   254 }

   255 

   256 

   257 /*  parser_newstobject(node* st)

   258  *

   259  *  Allocates a new Python object representing an ST.  This is simply the

   260  *  'wrapper' object that holds a node* and allows it to be passed around in

   261  *  Python code.

   262  *

   263  */

   264 static PyObject*

   265 parser_newstobject(node *st, int type)

   266 {

   267     PyST_Object* o = PyObject_New(PyST_Object, &PyST_Type);

   268 

   269     if (o != 0) {

   270         o->st_node = st;

   271         o->st_type = type;

   272         o->st_flags.cf_flags = 0;

   273     }

   274     else {

   275         PyNode_Free(st);

   276     }

   277     return ((PyObject*)o);

   278 }

   279 

   280 

   281 /*  void parser_free(PyST_Object* st)

   282  *

   283  *  This is called by a del statement that reduces the reference count to 0.

   284  *

   285  */

   286 static void

   287 parser_free(PyST_Object *st)

   288 {

   289     PyNode_Free(st->st_node);

   290     PyObject_Del(st);

   291 }

   292 

   293 

   294 /*  parser_st2tuple(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 ST object is not modified.

   298  *

   299  */

   300 static PyObject*

   301 parser_st2tuple(PyST_Object *self, PyObject *args, PyObject *kw)

   302 {

   303     PyObject *line_option = 0;

   304     PyObject *col_option = 0;

   305     PyObject *res = 0;

   306     int ok;

   307 

   308     static char *keywords[] = {"ast", "line_info", "col_info", NULL};

   309 

   310     if (self == NULL) {

   311         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|OO:st2tuple", keywords,

   312                                          &PyST_Type, &self, &line_option,

   313                                          &col_option);

   314     }

   315     else

   316         ok = PyArg_ParseTupleAndKeywords(args, kw, "|OO:totuple", &keywords[1],

   317                                          &line_option, &col_option);

   318     if (ok != 0) {

   319         int lineno = 0;

   320         int col_offset = 0;

   321         if (line_option != NULL) {

   322             lineno = (PyObject_IsTrue(line_option) != 0) ? 1 : 0;

   323         }

   324         if (col_option != NULL) {

   325             col_offset = (PyObject_IsTrue(col_option) != 0) ? 1 : 0;

   326         }

   327         /*

   328          *  Convert ST into a tuple representation.  Use Guido's function,

   329          *  since it's known to work already.

   330          */

   331         res = node2tuple(((PyST_Object*)self)->st_node,

   332                          PyTuple_New, PyTuple_SetItem, lineno, col_offset);

   333     }

   334     return (res);

   335 }

   336 

   337 static PyObject*

   338 parser_ast2tuple(PyST_Object *self, PyObject *args, PyObject *kw)

   339 {

   340     if (PyErr_WarnPy3k("ast2tuple is removed in 3.x; use st2tuple", 1) < 0)

   341         return NULL;

   342     return parser_st2tuple(self, args, kw);

   343 }

   344 

   345 

   346 /*  parser_st2list(PyObject* self, PyObject* args, PyObject* kw)

   347  *

   348  *  This provides conversion from a node* to a list object that can be

   349  *  returned to the Python-level caller.  The ST object is not modified.

   350  *

   351  */

   352 static PyObject*

   353 parser_st2list(PyST_Object *self, PyObject *args, PyObject *kw)

   354 {

   355     PyObject *line_option = 0;

   356     PyObject *col_option = 0;

   357     PyObject *res = 0;

   358     int ok;

   359 

   360     static char *keywords[] = {"ast", "line_info", "col_info", NULL};

   361 

   362     if (self == NULL)

   363         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|OO:st2list", keywords,

   364                                          &PyST_Type, &self, &line_option,

   365                                          &col_option);

   366     else

   367         ok = PyArg_ParseTupleAndKeywords(args, kw, "|OO:tolist", &keywords[1],

   368                                          &line_option, &col_option);

   369     if (ok) {

   370         int lineno = 0;

   371         int col_offset = 0;

   372         if (line_option != 0) {

   373             lineno = PyObject_IsTrue(line_option) ? 1 : 0;

   374         }

   375         if (col_option != NULL) {

   376             col_offset = (PyObject_IsTrue(col_option) != 0) ? 1 : 0;

   377         }

   378         /*

   379          *  Convert ST into a tuple representation.  Use Guido's function,

   380          *  since it's known to work already.

   381          */

   382         res = node2tuple(self->st_node,

   383                          PyList_New, PyList_SetItem, lineno, col_offset);

   384     }

   385     return (res);

   386 }

   387 

   388 static PyObject*

   389 parser_ast2list(PyST_Object *self, PyObject *args, PyObject *kw)

   390 {

   391     if (PyErr_WarnPy3k("ast2list is removed in 3.x; use st2list", 1) < 0)

   392         return NULL;

   393     return parser_st2list(self, args, kw);

   394 }

   395 

   396 

   397 /*  parser_compilest(PyObject* self, PyObject* args)

   398  *

   399  *  This function creates code objects from the parse tree represented by

   400  *  the passed-in data object.  An optional file name is passed in as well.

   401  *

   402  */

   403 static PyObject*

   404 parser_compilest(PyST_Object *self, PyObject *args, PyObject *kw)

   405 {

   406     PyObject*     res = 0;

   407     PyArena*      arena;

   408     mod_ty        mod;

   409     char*         str = "<syntax-tree>";

   410     int ok;

   411 

   412     static char *keywords[] = {"ast", "filename", NULL};

   413 

   414     if (self == NULL)

   415         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|s:compilest", keywords,

   416                                          &PyST_Type, &self, &str);

   417     else

   418         ok = PyArg_ParseTupleAndKeywords(args, kw, "|s:compile", &keywords[1],

   419                                          &str);

   420 

   421     if (ok) {

   422         arena = PyArena_New();

   423         if (arena) {

   424            mod = PyAST_FromNode(self->st_node, &(self->st_flags), str, arena);

   425            if (mod) {

   426                res = (PyObject *)PyAST_Compile(mod, str, &(self->st_flags), arena);

   427            }

   428            PyArena_Free(arena);

   429         }

   430     }

   431 

   432     return (res);

   433 }

   434 

   435 static PyObject*

   436 parser_compileast(PyST_Object *self, PyObject *args, PyObject *kw)

   437 {

   438     if (PyErr_WarnPy3k("compileast is removed in 3.x; use compilest", 1) < 0)

   439         return NULL;

   440     return parser_compilest(self, args, kw);

   441 }

   442 

   443 

   444 /*  PyObject* parser_isexpr(PyObject* self, PyObject* args)

   445  *  PyObject* parser_issuite(PyObject* self, PyObject* args)

   446  *

   447  *  Checks the passed-in ST object to determine if it is an expression or

   448  *  a statement suite, respectively.  The return is a Python truth value.

   449  *

   450  */

   451 static PyObject*

   452 parser_isexpr(PyST_Object *self, PyObject *args, PyObject *kw)

   453 {

   454     PyObject* res = 0;

   455     int ok;

   456 

   457     static char *keywords[] = {"ast", NULL};

   458 

   459     if (self == NULL)

   460         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!:isexpr", keywords,

   461                                          &PyST_Type, &self);

   462     else

   463         ok = PyArg_ParseTupleAndKeywords(args, kw, ":isexpr", &keywords[1]);

   464 

   465     if (ok) {

   466         /* Check to see if the ST represents an expression or not. */

   467         res = (self->st_type == PyST_EXPR) ? Py_True : Py_False;

   468         Py_INCREF(res);

   469     }

   470     return (res);

   471 }

   472 

   473 

   474 static PyObject*

   475 parser_issuite(PyST_Object *self, PyObject *args, PyObject *kw)

   476 {

   477     PyObject* res = 0;

   478     int ok;

   479 

   480     static char *keywords[] = {"ast", NULL};

   481 

   482     if (self == NULL)

   483         ok = PyArg_ParseTupleAndKeywords(args, kw, "O!:issuite", keywords,

   484                                          &PyST_Type, &self);

   485     else

   486         ok = PyArg_ParseTupleAndKeywords(args, kw, ":issuite", &keywords[1]);

   487 

   488     if (ok) {

   489         /* Check to see if the ST represents an expression or not. */

   490         res = (self->st_type == PyST_EXPR) ? Py_False : Py_True;

   491         Py_INCREF(res);

   492     }

   493     return (res);

   494 }

   495 

   496 

   497 #define PUBLIC_METHOD_TYPE (METH_VARARGS|METH_KEYWORDS)

   498 

   499 static PyMethodDef

   500 parser_methods[] = {

   501     {"compile",         (PyCFunction)parser_compilest,  PUBLIC_METHOD_TYPE,

   502         PyDoc_STR("Compile this ST object into a code object.")},

   503     {"isexpr",          (PyCFunction)parser_isexpr,     PUBLIC_METHOD_TYPE,

   504         PyDoc_STR("Determines if this ST object was created from an expression.")},

   505     {"issuite",         (PyCFunction)parser_issuite,    PUBLIC_METHOD_TYPE,

   506         PyDoc_STR("Determines if this ST object was created from a suite.")},

   507     {"tolist",          (PyCFunction)parser_st2list,    PUBLIC_METHOD_TYPE,

   508         PyDoc_STR("Creates a list-tree representation of this ST.")},

   509     {"totuple",         (PyCFunction)parser_st2tuple,   PUBLIC_METHOD_TYPE,

   510         PyDoc_STR("Creates a tuple-tree representation of this ST.")},

   511 

   512     {NULL, NULL, 0, NULL}

   513 };

   514 

   515 

   516 static PyObject*

   517 parser_getattr(PyObject *self, char *name)

   518 {

   519     return (Py_FindMethod(parser_methods, self, name));

   520 }

   521 

   522 

   523 /*  err_string(char* message)

   524  *

   525  *  Sets the error string for an exception of type ParserError.

   526  *

   527  */

   528 static void

   529 err_string(char *message)

   530 {

   531     PyErr_SetString(parser_error, message);

   532 }

   533 

   534 

   535 /*  PyObject* parser_do_parse(PyObject* args, int type)

   536  *

   537  *  Internal function to actually execute the parse and return the result if

   538  *  successful or set an exception if not.

   539  *

   540  */

   541 static PyObject*

   542 parser_do_parse(PyObject *args, PyObject *kw, char *argspec, int type)

   543 {

   544     char*     string = 0;

   545     PyObject* res    = 0;

   546     int flags        = 0;

   547     perrdetail err;

   548 

   549     static char *keywords[] = {"source", NULL};

   550 

   551     if (PyArg_ParseTupleAndKeywords(args, kw, argspec, keywords, &string)) {

   552         node* n = PyParser_ParseStringFlagsFilenameEx(string, NULL,

   553                                                        &_PyParser_Grammar,

   554                                                       (type == PyST_EXPR)

   555                                                       ? eval_input : file_input,

   556                                                       &err, &flags);

   557 

   558 	if (n) {

   559 	    res = parser_newstobject(n, type);

   560             if (res)

   561                 ((PyST_Object *)res)->st_flags.cf_flags = flags & PyCF_MASK;

   562         }

   563         else

   564             PyParser_SetError(&err);

   565     }

   566     return (res);

   567 }

   568 

   569 

   570 /*  PyObject* parser_expr(PyObject* self, PyObject* args)

   571  *  PyObject* parser_suite(PyObject* self, PyObject* args)

   572  *

   573  *  External interfaces to the parser itself.  Which is called determines if

   574  *  the parser attempts to recognize an expression ('eval' form) or statement

   575  *  suite ('exec' form).  The real work is done by parser_do_parse() above.

   576  *

   577  */

   578 static PyObject*

   579 parser_expr(PyST_Object *self, PyObject *args, PyObject *kw)

   580 {

   581     NOTE(ARGUNUSED(self))

   582     return (parser_do_parse(args, kw, "s:expr", PyST_EXPR));

   583 }

   584 

   585 

   586 static PyObject*

   587 parser_suite(PyST_Object *self, PyObject *args, PyObject *kw)

   588 {

   589     NOTE(ARGUNUSED(self))

   590     return (parser_do_parse(args, kw, "s:suite", PyST_SUITE));

   591 }

   592 

   593 

   594 

   595 /*  This is the messy part of the code.  Conversion from a tuple to an ST

   596  *  object requires that the input tuple be valid without having to rely on

   597  *  catching an exception from the compiler.  This is done to allow the

   598  *  compiler itself to remain fast, since most of its input will come from

   599  *  the parser directly, and therefore be known to be syntactically correct.

   600  *  This validation is done to ensure that we don't core dump the compile

   601  *  phase, returning an exception instead.

   602  *

   603  *  Two aspects can be broken out in this code:  creating a node tree from

   604  *  the tuple passed in, and verifying that it is indeed valid.  It may be

   605  *  advantageous to expand the number of ST types to include funcdefs and

   606  *  lambdadefs to take advantage of the optimizer, recognizing those STs

   607  *  here.  They are not necessary, and not quite as useful in a raw form.

   608  *  For now, let's get expressions and suites working reliably.

   609  */

   610 

   611 

   612 static node* build_node_tree(PyObject *tuple);

   613 static int   validate_expr_tree(node *tree);

   614 static int   validate_file_input(node *tree);

   615 static int   validate_encoding_decl(node *tree);

   616 

   617 /*  PyObject* parser_tuple2st(PyObject* self, PyObject* args)

   618  *

   619  *  This is the public function, called from the Python code.  It receives a

   620  *  single tuple object from the caller, and creates an ST object if the

   621  *  tuple can be validated.  It does this by checking the first code of the

   622  *  tuple, and, if acceptable, builds the internal representation.  If this

   623  *  step succeeds, the internal representation is validated as fully as

   624  *  possible with the various validate_*() routines defined below.

   625  *

   626  *  This function must be changed if support is to be added for PyST_FRAGMENT

   627  *  ST objects.

   628  *

   629  */

   630 static PyObject*

   631 parser_tuple2st(PyST_Object *self, PyObject *args, PyObject *kw)

   632 {

   633     NOTE(ARGUNUSED(self))

   634     PyObject *st = 0;

   635     PyObject *tuple;

   636     node *tree;

   637 

   638     static char *keywords[] = {"sequence", NULL};

   639 

   640     if (!PyArg_ParseTupleAndKeywords(args, kw, "O:sequence2st", keywords,

   641                                      &tuple))

   642         return (0);

   643     if (!PySequence_Check(tuple)) {

   644         PyErr_SetString(PyExc_ValueError,

   645                         "sequence2st() requires a single sequence argument");

   646         return (0);

   647     }

   648     /*

   649      *  Convert the tree to the internal form before checking it.

   650      */

   651     tree = build_node_tree(tuple);

   652     if (tree != 0) {

   653         int start_sym = TYPE(tree);

   654         if (start_sym == eval_input) {

   655             /*  Might be an eval form.  */

   656             if (validate_expr_tree(tree))

   657                 st = parser_newstobject(tree, PyST_EXPR);

   658             else

   659                 PyNode_Free(tree);

   660         }

   661         else if (start_sym == file_input) {

   662             /*  This looks like an exec form so far.  */

   663             if (validate_file_input(tree))

   664                 st = parser_newstobject(tree, PyST_SUITE);

   665             else

   666                 PyNode_Free(tree);

   667         }

   668         else if (start_sym == encoding_decl) {

   669             /* This looks like an encoding_decl so far. */

   670             if (validate_encoding_decl(tree))

   671                 st = parser_newstobject(tree, PyST_SUITE);

   672             else

   673                 PyNode_Free(tree);

   674         }

   675         else {

   676             /*  This is a fragment, at best. */

   677             PyNode_Free(tree);

   678             err_string("parse tree does not use a valid start symbol");

   679         }

   680     }

   681     /*  Make sure we throw an exception on all errors.  We should never

   682      *  get this, but we'd do well to be sure something is done.

   683      */

   684     if (st == NULL && !PyErr_Occurred())

   685         err_string("unspecified ST error occurred");

   686 

   687     return st;

   688 }

   689 

   690 static PyObject*

   691 parser_tuple2ast(PyST_Object *self, PyObject *args, PyObject *kw)

   692 {

   693     if (PyErr_WarnPy3k("tuple2ast is removed in 3.x; use tuple2st", 1) < 0)

   694         return NULL;

   695     return parser_tuple2st(self, args, kw);

   696 }

   697 

   698 

   699 /*  node* build_node_children()

   700  *

   701  *  Iterate across the children of the current non-terminal node and build

   702  *  their structures.  If successful, return the root of this portion of

   703  *  the tree, otherwise, 0.  Any required exception will be specified already,

   704  *  and no memory will have been deallocated.

   705  *

   706  */

   707 static node*

   708 build_node_children(PyObject *tuple, node *root, int *line_num)

   709 {

   710     Py_ssize_t len = PyObject_Size(tuple);

   711     Py_ssize_t i;

   712     int  err;

   713 

   714     for (i = 1; i < len; ++i) {

   715         /* elem must always be a sequence, however simple */

   716         PyObject* elem = PySequence_GetItem(tuple, i);

   717         int ok = elem != NULL;

   718         long  type = 0;

   719         char *strn = 0;

   720 

   721         if (ok)

   722             ok = PySequence_Check(elem);

   723         if (ok) {

   724             PyObject *temp = PySequence_GetItem(elem, 0);

   725             if (temp == NULL)

   726                 ok = 0;

   727             else {

   728                 ok = PyInt_Check(temp);

   729                 if (ok)

   730                     type = PyInt_AS_LONG(temp);

   731                 Py_DECREF(temp);

   732             }

   733         }

   734         if (!ok) {

   735             PyObject *err = Py_BuildValue("os", elem,

   736                                           "Illegal node construct.");

   737             PyErr_SetObject(parser_error, err);

   738             Py_XDECREF(err);

   739             Py_XDECREF(elem);

   740             return (0);

   741         }

   742         if (ISTERMINAL(type)) {

   743             Py_ssize_t len = PyObject_Size(elem);

   744             PyObject *temp;

   745 

   746             if ((len != 2) && (len != 3)) {

   747                 err_string("terminal nodes must have 2 or 3 entries");

   748                 return 0;

   749             }

   750             temp = PySequence_GetItem(elem, 1);

   751             if (temp == NULL)

   752                 return 0;

   753             if (!PyString_Check(temp)) {

   754                 PyErr_Format(parser_error,

   755                              "second item in terminal node must be a string,"

   756                              " found %s",

   757                              Py_TYPE(temp)->tp_name);

   758                 Py_DECREF(temp);

   759                 return 0;

   760             }

   761             if (len == 3) {

   762                 PyObject *o = PySequence_GetItem(elem, 2);

   763                 if (o != NULL) {

   764                     if (PyInt_Check(o))

   765                         *line_num = PyInt_AS_LONG(o);

   766                     else {

   767                         PyErr_Format(parser_error,

   768                                      "third item in terminal node must be an"

   769                                      " integer, found %s",

   770 				     Py_TYPE(temp)->tp_name);

   771                         Py_DECREF(o);

   772                         Py_DECREF(temp);

   773                         return 0;

   774                     }

   775                     Py_DECREF(o);

   776                 }

   777             }

   778             len = PyString_GET_SIZE(temp) + 1;

   779             strn = (char *)PyObject_MALLOC(len);

   780             if (strn != NULL)

   781                 (void) memcpy(strn, PyString_AS_STRING(temp), len);

   782             Py_DECREF(temp);

   783         }

   784         else if (!ISNONTERMINAL(type)) {

   785             /*

   786              *  It has to be one or the other; this is an error.

   787              *  Throw an exception.

   788              */

   789             PyObject *err = Py_BuildValue("os", elem, "unknown node type.");

   790             PyErr_SetObject(parser_error, err);

   791             Py_XDECREF(err);

   792             Py_XDECREF(elem);

   793             return (0);

   794         }

   795         err = PyNode_AddChild(root, type, strn, *line_num, 0);

   796         if (err == E_NOMEM) {

   797             PyObject_FREE(strn);

   798             return (node *) PyErr_NoMemory();

   799         }

   800         if (err == E_OVERFLOW) {

   801             PyObject_FREE(strn);

   802             PyErr_SetString(PyExc_ValueError,

   803                             "unsupported number of child nodes");

   804             return NULL;

   805         }

   806 

   807         if (ISNONTERMINAL(type)) {

   808             node* new_child = CHILD(root, i - 1);

   809 

   810             if (new_child != build_node_children(elem, new_child, line_num)) {

   811                 Py_XDECREF(elem);

   812                 return (0);

   813             }

   814         }

   815         else if (type == NEWLINE) {     /* It's true:  we increment the     */

   816             ++(*line_num);              /* line number *after* the newline! */

   817         }

   818         Py_XDECREF(elem);

   819     }

   820     return root;

   821 }

   822 

   823 

   824 static node*

   825 build_node_tree(PyObject *tuple)

   826 {

   827     node* res = 0;

   828     PyObject *temp = PySequence_GetItem(tuple, 0);

   829     long num = -1;

   830 

   831     if (temp != NULL)

   832         num = PyInt_AsLong(temp);

   833     Py_XDECREF(temp);

   834     if (ISTERMINAL(num)) {

   835         /*

   836          *  The tuple is simple, but it doesn't start with a start symbol.

   837          *  Throw an exception now and be done with it.

   838          */

   839         tuple = Py_BuildValue("os", tuple,

   840                     "Illegal syntax-tree; cannot start with terminal symbol.");

   841         PyErr_SetObject(parser_error, tuple);

   842         Py_XDECREF(tuple);

   843     }

   844     else if (ISNONTERMINAL(num)) {

   845         /*

   846          *  Not efficient, but that can be handled later.

   847          */

   848         int line_num = 0;

   849         PyObject *encoding = NULL;

   850 

   851         if (num == encoding_decl) {

   852             encoding = PySequence_GetItem(tuple, 2);

   853             /* tuple isn't borrowed anymore here, need to DECREF */

   854             tuple = PySequence_GetSlice(tuple, 0, 2);

   855         }

   856         res = PyNode_New(num);

   857         if (res != NULL) {

   858             if (res != build_node_children(tuple, res, &line_num)) {

   859                 PyNode_Free(res);

   860                 res = NULL;

   861             }

   862             if (res && encoding) {

   863                 Py_ssize_t len;

   864                 len = PyString_GET_SIZE(encoding) + 1;

   865                 res->n_str = (char *)PyObject_MALLOC(len);

   866                 if (res->n_str != NULL)

   867                     (void) memcpy(res->n_str, PyString_AS_STRING(encoding), len);

   868                 Py_DECREF(encoding);

   869                 Py_DECREF(tuple);

   870             }

   871         }

   872     }

   873     else {

   874         /*  The tuple is illegal -- if the number is neither TERMINAL nor

   875          *  NONTERMINAL, we can't use it.  Not sure the implementation

   876          *  allows this condition, but the API doesn't preclude it.

   877          */

   878         PyObject *err = Py_BuildValue("os", tuple,

   879                                       "Illegal component tuple.");

   880         PyErr_SetObject(parser_error, err);

   881         Py_XDECREF(err);

   882     }

   883 

   884     return (res);

   885 }

   886 

   887 

   888 /*

   889  *  Validation routines used within the validation section:

   890  */

   891 static int validate_terminal(node *terminal, int type, char *string);

   892 

   893 #define validate_ampersand(ch)  validate_terminal(ch,      AMPER, "&")

   894 #define validate_circumflex(ch) validate_terminal(ch, CIRCUMFLEX, "^")

   895 #define validate_colon(ch)      validate_terminal(ch,      COLON, ":")

   896 #define validate_comma(ch)      validate_terminal(ch,      COMMA, ",")

   897 #define validate_dedent(ch)     validate_terminal(ch,     DEDENT, "")

   898 #define validate_equal(ch)      validate_terminal(ch,      EQUAL, "=")

   899 #define validate_indent(ch)     validate_terminal(ch,     INDENT, (char*)NULL)

   900 #define validate_lparen(ch)     validate_terminal(ch,       LPAR, "(")

   901 #define validate_newline(ch)    validate_terminal(ch,    NEWLINE, (char*)NULL)

   902 #define validate_rparen(ch)     validate_terminal(ch,       RPAR, ")")

   903 #define validate_semi(ch)       validate_terminal(ch,       SEMI, ";")

   904 #define validate_star(ch)       validate_terminal(ch,       STAR, "*")

   905 #define validate_vbar(ch)       validate_terminal(ch,       VBAR, "|")

   906 #define validate_doublestar(ch) validate_terminal(ch, DOUBLESTAR, "**")

   907 #define validate_dot(ch)        validate_terminal(ch,        DOT, ".")

   908 #define validate_at(ch)         validate_terminal(ch,         AT, "@")

   909 #define validate_name(ch, str)  validate_terminal(ch,       NAME, str)

   910 

   911 #define VALIDATER(n)    static int validate_##n(node *tree)

   912 

   913 VALIDATER(node);                VALIDATER(small_stmt);

   914 VALIDATER(class);               VALIDATER(node);

   915 VALIDATER(parameters);          VALIDATER(suite);

   916 VALIDATER(testlist);            VALIDATER(varargslist);

   917 VALIDATER(fpdef);               VALIDATER(fplist);

   918 VALIDATER(stmt);                VALIDATER(simple_stmt);

   919 VALIDATER(expr_stmt);           VALIDATER(power);

   920 VALIDATER(print_stmt);          VALIDATER(del_stmt);

   921 VALIDATER(return_stmt);         VALIDATER(list_iter);

   922 VALIDATER(raise_stmt);          VALIDATER(import_stmt);

   923 VALIDATER(import_name);         VALIDATER(import_from);

   924 VALIDATER(global_stmt);         VALIDATER(list_if);

   925 VALIDATER(assert_stmt);         VALIDATER(list_for);

   926 VALIDATER(exec_stmt);           VALIDATER(compound_stmt);

   927 VALIDATER(while);               VALIDATER(for);

   928 VALIDATER(try);                 VALIDATER(except_clause);

   929 VALIDATER(test);                VALIDATER(and_test);

   930 VALIDATER(not_test);            VALIDATER(comparison);

   931 VALIDATER(comp_op);             VALIDATER(expr);

   932 VALIDATER(xor_expr);            VALIDATER(and_expr);

   933 VALIDATER(shift_expr);          VALIDATER(arith_expr);

   934 VALIDATER(term);                VALIDATER(factor);

   935 VALIDATER(atom);                VALIDATER(lambdef);

   936 VALIDATER(trailer);             VALIDATER(subscript);

   937 VALIDATER(subscriptlist);       VALIDATER(sliceop);

   938 VALIDATER(exprlist);            VALIDATER(dictmaker);

   939 VALIDATER(arglist);             VALIDATER(argument);

   940 VALIDATER(listmaker);           VALIDATER(yield_stmt);

   941 VALIDATER(testlist1);           VALIDATER(gen_for);

   942 VALIDATER(gen_iter);            VALIDATER(gen_if);

   943 VALIDATER(testlist_gexp);	VALIDATER(yield_expr);

   944 VALIDATER(yield_or_testlist);	VALIDATER(or_test);

   945 VALIDATER(old_test); 		VALIDATER(old_lambdef);

   946 

   947 #undef VALIDATER

   948 

   949 #define is_even(n)      (((n) & 1) == 0)

   950 #define is_odd(n)       (((n) & 1) == 1)

   951 

   952 

   953 static int

   954 validate_ntype(node *n, int t)

   955 {

   956     if (TYPE(n) != t) {

   957         PyErr_Format(parser_error, "Expected node type %d, got %d.",

   958                      t, TYPE(n));

   959         return 0;

   960     }

   961     return 1;

   962 }

   963 

   964 

   965 /*  Verifies that the number of child nodes is exactly 'num', raising

   966  *  an exception if it isn't.  The exception message does not indicate

   967  *  the exact number of nodes, allowing this to be used to raise the

   968  *  "right" exception when the wrong number of nodes is present in a

   969  *  specific variant of a statement's syntax.  This is commonly used

   970  *  in that fashion.

   971  */

   972 static int

   973 validate_numnodes(node *n, int num, const char *const name)

   974 {

   975     if (NCH(n) != num) {

   976         PyErr_Format(parser_error,

   977                      "Illegal number of children for %s node.", name);

   978         return 0;

   979     }

   980     return 1;

   981 }

   982 

   983 

   984 static int

   985 validate_terminal(node *terminal, int type, char *string)

   986 {

   987     int res = (validate_ntype(terminal, type)

   988                && ((string == 0) || (strcmp(string, STR(terminal)) == 0)));

   989 

   990     if (!res && !PyErr_Occurred()) {

   991         PyErr_Format(parser_error,

   992                      "Illegal terminal: expected \"%s\"", string);

   993     }

   994     return (res);

   995 }

   996 

   997 

   998 /*  X (',' X) [',']

   999  */

  1000 static int

  1001 validate_repeating_list(node *tree, int ntype, int (*vfunc)(node *),

  1002                         const char *const name)

  1003 {

  1004     int nch = NCH(tree);

  1005     int res = (nch && validate_ntype(tree, ntype)

  1006                && vfunc(CHILD(tree, 0)));

  1007 

  1008     if (!res && !PyErr_Occurred())

  1009         (void) validate_numnodes(tree, 1, name);

  1010     else {

  1011         if (is_even(nch))

  1012             res = validate_comma(CHILD(tree, --nch));

  1013         if (res && nch > 1) {

  1014             int pos = 1;

  1015             for ( ; res && pos < nch; pos += 2)

  1016                 res = (validate_comma(CHILD(tree, pos))

  1017                        && vfunc(CHILD(tree, pos + 1)));

  1018         }

  1019     }

  1020     return (res);

  1021 }

  1022 

  1023 

  1024 /*  validate_class()

  1025  *

  1026  *  classdef:

  1027  *      'class' NAME ['(' testlist ')'] ':' suite

  1028  */

  1029 static int

  1030 validate_class(node *tree)

  1031 {

  1032     int nch = NCH(tree);

  1033     int res = (validate_ntype(tree, classdef) &&

  1034 	       	((nch == 4) || (nch == 6) || (nch == 7)));

  1035 

  1036     if (res) {

  1037         res = (validate_name(CHILD(tree, 0), "class")

  1038                && validate_ntype(CHILD(tree, 1), NAME)

  1039                && validate_colon(CHILD(tree, nch - 2))

  1040                && validate_suite(CHILD(tree, nch - 1)));

  1041     }

  1042     else {

  1043         (void) validate_numnodes(tree, 4, "class");

  1044     }

  1045 	

  1046     if (res) {

  1047 	if (nch == 7) {

  1048 		res = ((validate_lparen(CHILD(tree, 2)) &&

  1049 			validate_testlist(CHILD(tree, 3)) &&

  1050 			validate_rparen(CHILD(tree, 4))));

  1051 	}

  1052 	else if (nch == 6) {

  1053 		res = (validate_lparen(CHILD(tree,2)) &&

  1054 			validate_rparen(CHILD(tree,3)));

  1055 	}

  1056     }

  1057     return (res);

  1058 }

  1059 

  1060 

  1061 /*  if_stmt:

  1062  *      'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

  1063  */

  1064 static int

  1065 validate_if(node *tree)

  1066 {

  1067     int nch = NCH(tree);

  1068     int res = (validate_ntype(tree, if_stmt)

  1069                && (nch >= 4)

  1070                && validate_name(CHILD(tree, 0), "if")

  1071                && validate_test(CHILD(tree, 1))

  1072                && validate_colon(CHILD(tree, 2))

  1073                && validate_suite(CHILD(tree, 3)));

  1074 

  1075     if (res && ((nch % 4) == 3)) {

  1076         /*  ... 'else' ':' suite  */

  1077         res = (validate_name(CHILD(tree, nch - 3), "else")

  1078                && validate_colon(CHILD(tree, nch - 2))

  1079                && validate_suite(CHILD(tree, nch - 1)));

  1080         nch -= 3;

  1081     }

  1082     else if (!res && !PyErr_Occurred())

  1083         (void) validate_numnodes(tree, 4, "if");

  1084     if ((nch % 4) != 0)

  1085         /* Will catch the case for nch < 4 */

  1086         res = validate_numnodes(tree, 0, "if");

  1087     else if (res && (nch > 4)) {

  1088         /*  ... ('elif' test ':' suite)+ ...  */

  1089         int j = 4;

  1090         while ((j < nch) && res) {

  1091             res = (validate_name(CHILD(tree, j), "elif")

  1092                    && validate_colon(CHILD(tree, j + 2))

  1093                    && validate_test(CHILD(tree, j + 1))

  1094                    && validate_suite(CHILD(tree, j + 3)));

  1095             j += 4;

  1096         }

  1097     }

  1098     return (res);

  1099 }

  1100 

  1101 

  1102 /*  parameters:

  1103  *      '(' [varargslist] ')'

  1104  *

  1105  */

  1106 static int

  1107 validate_parameters(node *tree)

  1108 {

  1109     int nch = NCH(tree);

  1110     int res = validate_ntype(tree, parameters) && ((nch == 2) || (nch == 3));

  1111 

  1112     if (res) {

  1113         res = (validate_lparen(CHILD(tree, 0))

  1114                && validate_rparen(CHILD(tree, nch - 1)));

  1115         if (res && (nch == 3))

  1116             res = validate_varargslist(CHILD(tree, 1));

  1117     }

  1118     else {

  1119         (void) validate_numnodes(tree, 2, "parameters");

  1120     }

  1121     return (res);

  1122 }

  1123 

  1124 

  1125 /*  validate_suite()

  1126  *

  1127  *  suite:

  1128  *      simple_stmt

  1129  *    | NEWLINE INDENT stmt+ DEDENT

  1130  */

  1131 static int

  1132 validate_suite(node *tree)

  1133 {

  1134     int nch = NCH(tree);

  1135     int res = (validate_ntype(tree, suite) && ((nch == 1) || (nch >= 4)));