1 /* Parse tree node implementation */
2
3 #include "Python.h"
4 #include "../Include/node.h"
5 #include "../Include/errcode.h"
6
7 node *
Ta27Node_New(int type)8 Ta27Node_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 Ta27Node_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 * Ta27Node_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
Ta27Node_AddChild(register node * n1,int type,char * str,int lineno,int col_offset)79 Ta27Node_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 ((size_t)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
Ta27Node_Free(node * n)121 Ta27Node_Free(node *n)
122 {
123 if (n != NULL) {
124 freechildren(n);
125 PyObject_FREE(n);
126 }
127 }
128
129 Py_ssize_t
_Ta27Node_SizeOf(node * n)130 _Ta27Node_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