Line data Source code
1 : /* Parse tree node implementation */
2 :
3 : #include "Python.h"
4 : #include "node.h"
5 : #include "errcode.h"
6 :
7 : node *
8 6 : PyNode_New(int type)
9 : {
10 6 : node *n = (node *) PyObject_MALLOC(1 * sizeof(node));
11 6 : if (n == NULL)
12 0 : return NULL;
13 6 : n->n_type = type;
14 6 : n->n_str = NULL;
15 6 : n->n_lineno = 0;
16 6 : n->n_nchildren = 0;
17 6 : n->n_child = NULL;
18 6 : return n;
19 : }
20 :
21 : /* See comments at XXXROUNDUP below. Returns -1 on overflow. */
22 : static int
23 0 : fancy_roundup(int n)
24 : {
25 : /* Round up to the closest power of 2 >= n. */
26 0 : int result = 256;
27 : assert(n > 128);
28 0 : while (result < n) {
29 0 : result <<= 1;
30 0 : if (result <= 0)
31 0 : return -1;
32 : }
33 0 : 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 9244 : PyNode_AddChild(register node *n1, int type, char *str, int lineno, int col_offset)
80 : {
81 9244 : const int nch = n1->n_nchildren;
82 : int current_capacity;
83 : int required_capacity;
84 : node *n;
85 :
86 9244 : if (nch == INT_MAX || nch < 0)
87 0 : return E_OVERFLOW;
88 :
89 9244 : current_capacity = XXXROUNDUP(nch);
90 9244 : required_capacity = XXXROUNDUP(nch + 1);
91 9244 : if (current_capacity < 0 || required_capacity < 0)
92 0 : return E_OVERFLOW;
93 9244 : if (current_capacity < required_capacity) {
94 8453 : if (required_capacity > PY_SIZE_MAX / sizeof(node)) {
95 0 : return E_NOMEM;
96 : }
97 8453 : n = n1->n_child;
98 8453 : n = (node *) PyObject_REALLOC(n,
99 : required_capacity * sizeof(node));
100 8453 : if (n == NULL)
101 0 : return E_NOMEM;
102 8453 : n1->n_child = n;
103 : }
104 :
105 9244 : n = &n1->n_child[n1->n_nchildren++];
106 9244 : n->n_type = type;
107 9244 : n->n_str = str;
108 9244 : n->n_lineno = lineno;
109 9244 : n->n_col_offset = col_offset;
110 9244 : n->n_nchildren = 0;
111 9244 : n->n_child = NULL;
112 9244 : return 0;
113 : }
114 :
115 : /* Forward */
116 : static void freechildren(node *);
117 : static Py_ssize_t sizeofchildren(node *n);
118 :
119 :
120 : void
121 6 : PyNode_Free(node *n)
122 : {
123 6 : if (n != NULL) {
124 3 : freechildren(n);
125 3 : PyObject_FREE(n);
126 : }
127 6 : }
128 :
129 : Py_ssize_t
130 0 : _PyNode_SizeOf(node *n)
131 : {
132 0 : Py_ssize_t res = 0;
133 :
134 0 : if (n != NULL)
135 0 : res = sizeof(node) + sizeofchildren(n);
136 0 : return res;
137 : }
138 :
139 : static void
140 9250 : freechildren(node *n)
141 : {
142 : int i;
143 27747 : for (i = NCH(n); --i >= 0; )
144 9247 : freechildren(CHILD(n, i));
145 9250 : if (n->n_child != NULL)
146 7427 : PyObject_FREE(n->n_child);
147 9250 : if (STR(n) != NULL)
148 1826 : PyObject_FREE(STR(n));
149 9250 : }
150 :
151 : static Py_ssize_t
152 0 : sizeofchildren(node *n)
153 : {
154 0 : Py_ssize_t res = 0;
155 : int i;
156 0 : for (i = NCH(n); --i >= 0; )
157 0 : res += sizeofchildren(CHILD(n, i));
158 0 : if (n->n_child != NULL)
159 : /* allocated size of n->n_child array */
160 0 : res += XXXROUNDUP(NCH(n)) * sizeof(node);
161 0 : if (STR(n) != NULL)
162 0 : res += strlen(STR(n)) + 1;
163 0 : return res;
164 : }
|
