• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* Parse tree node implementation */
2 
3 #include "Python.h"
4 #include "node.h"
5 #include "errcode.h"
6 
7 node *
PyNode_New(int type)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
fancy_roundup(int n)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
PyNode_AddChild(register node * n1,int type,char * str,int lineno,int col_offset)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
PyNode_Free(node * n)121 PyNode_Free(node *n)
122 {
123     if (n != NULL) {
124         freechildren(n);
125         PyObject_FREE(n);
126     }
127 }
128 
129 Py_ssize_t
_PyNode_SizeOf(node * n)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
freechildren(node * n)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
sizeofchildren(node * n)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