Python code coverage for Parser/node.c

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