Home | History | Annotate | Download | only in Parser 
      1 /* Parse tree node implementation */
      2 
      3 #include "Python.h"
      4 #include "node.h"
      5 #include "errcode.h"
      6 
      7 node *
      8 PyNode_New(int type)
      9 {
     10     node *n = (node *) PyObject_MALLOC(1 * sizeof(node));
     11     if (n == NULL)
     12         return NULL;
     13     n->n_type = type;
     14     n->n_str = NULL;
     15     n->n_lineno = 0;
     16     n->n_nchildren = 0;
     17     n->n_child = NULL;
     18     return n;
     19 }
     20 
     21 /* See comments at XXXROUNDUP below.  Returns -1 on overflow. */
     22 static int
     23 fancy_roundup(int n)
     24 {
     25     /* Round up to the closest power of 2 >= n. */
     26     int result = 256;
     27     assert(n > 128);
     28     while (result < n) {
     29         result <<= 1;
     30         if (result <= 0)
     31             return -1;
     32     }
     33     return result;
     34 }
     35 
     36 /* A gimmick to make massive numbers of reallocs quicker.  The result is
     37  * a number >= the input.  In PyNode_AddChild, it's used like so, when
     38  * we're about to add child number current_size + 1:
     39  *
     40  *     if XXXROUNDUP(current_size) < XXXROUNDUP(current_size + 1):
     41  *         allocate space for XXXROUNDUP(current_size + 1) total children
     42  *     else:
     43  *         we already have enough space
     44  *
     45  * Since a node starts out empty, we must have
     46  *
     47  *     XXXROUNDUP(0) < XXXROUNDUP(1)
     48  *
     49  * so that we allocate space for the first child.  One-child nodes are very
     50  * common (presumably that would change if we used a more abstract form
     51  * of syntax tree), so to avoid wasting memory it's desirable that
     52  * XXXROUNDUP(1) == 1.  That in turn forces XXXROUNDUP(0) == 0.
     53  *
     54  * Else for 2 <= n <= 128, we round up to the closest multiple of 4.  Why 4?
     55  * Rounding up to a multiple of an exact power of 2 is very efficient, and
     56  * most nodes with more than one child have <= 4 kids.
     57  *
     58  * Else we call fancy_roundup() to grow proportionately to n.  We've got an
     59  * extreme case then (like test_longexp.py), and on many platforms doing
     60  * anything less than proportional growth leads to exorbitant runtime
     61  * (e.g., MacPython), or extreme fragmentation of user address space (e.g.,
     62  * Win98).
     63  *
     64  * In a run of compileall across the 2.3a0 Lib directory, Andrew MacIntyre
     65  * reported that, with this scheme, 89% of PyObject_REALLOC calls in
     66  * PyNode_AddChild passed 1 for the size, and 9% passed 4.  So this usually
     67  * wastes very little memory, but is very effective at sidestepping
     68  * platform-realloc disasters on vulnerable platforms.
     69  *
     70  * Note that this would be straightforward if a node stored its current
     71  * capacity.  The code is tricky to avoid that.
     72  */
     73 #define XXXROUNDUP(n) ((n) <= 1 ? (n) :                 \
     74                (n) <= 128 ? (((n) + 3) & ~3) :          \
     75                fancy_roundup(n))
     76 
     77 
     78 int
     79 PyNode_AddChild(register node *n1, int type, char *str, int lineno, int col_offset)
     80 {
     81     const int nch = n1->n_nchildren;
     82     int current_capacity;
     83     int required_capacity;
     84     node *n;
     85 
     86     if (nch == INT_MAX || nch < 0)
     87         return E_OVERFLOW;
     88 
     89     current_capacity = XXXROUNDUP(nch);
     90     required_capacity = XXXROUNDUP(nch + 1);
     91     if (current_capacity < 0 || required_capacity < 0)
     92         return E_OVERFLOW;
     93     if (current_capacity < required_capacity) {
     94         if (required_capacity > PY_SIZE_MAX / sizeof(node)) {
     95             return E_NOMEM;
     96         }
     97         n = n1->n_child;
     98         n = (node *) PyObject_REALLOC(n,
     99                                       required_capacity * sizeof(node));
    100         if (n == NULL)
    101             return E_NOMEM;
    102         n1->n_child = n;
    103     }
    104 
    105     n = &n1->n_child[n1->n_nchildren++];
    106     n->n_type = type;
    107     n->n_str = str;
    108     n->n_lineno = lineno;
    109     n->n_col_offset = col_offset;
    110     n->n_nchildren = 0;
    111     n->n_child = NULL;
    112     return 0;
    113 }
    114 
    115 /* Forward */
    116 static void freechildren(node *);
    117 static Py_ssize_t sizeofchildren(node *n);
    118 
    119 
    120 void
    121 PyNode_Free(node *n)
    122 {
    123     if (n != NULL) {
    124         freechildren(n);
    125         PyObject_FREE(n);
    126     }
    127 }
    128 
    129 Py_ssize_t
    130 _PyNode_SizeOf(node *n)
    131 {
    132     Py_ssize_t res = 0;
    133 
    134     if (n != NULL)
    135         res = sizeof(node) + sizeofchildren(n);
    136     return res;
    137 }
    138 
    139 static void
    140 freechildren(node *n)
    141 {
    142     int i;
    143     for (i = NCH(n); --i >= 0; )
    144         freechildren(CHILD(n, i));
    145     if (n->n_child != NULL)
    146         PyObject_FREE(n->n_child);
    147     if (STR(n) != NULL)
    148         PyObject_FREE(STR(n));
    149 }
    150 
    151 static Py_ssize_t
    152 sizeofchildren(node *n)
    153 {
    154     Py_ssize_t res = 0;
    155     int i;
    156     for (i = NCH(n); --i >= 0; )
    157         res += sizeofchildren(CHILD(n, i));
    158     if (n->n_child != NULL)
    159         /* allocated size of n->n_child array */
    160         res += XXXROUNDUP(NCH(n)) * sizeof(node);
    161     if (STR(n) != NULL)
    162         res += strlen(STR(n)) + 1;
    163     return res;
    164 }
    165