blob: f4c86cb0ff5c836998fb765ffd1b9bf7bfe09659 [file] [log] [blame]
Vladimir Marangozov58e64a82000-09-03 23:47:08 +00001/* Parse tree node implementation */
2
Tim Peters1d6a7292000-09-26 06:11:54 +00003#include "Python.h"
Vladimir Marangozov58e64a82000-09-03 23:47:08 +00004#include "node.h"
5#include "errcode.h"
6
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00007node *
Thomas Wouters23c9e002000-07-22 19:20:54 +00008PyNode_New(int type)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00009{
Andrew MacIntyre80d4e2a2002-08-04 06:28:21 +000010 node *n = (node *) PyObject_MALLOC(1 * sizeof(node));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000011 if (n == NULL)
12 return NULL;
13 n->n_type = type;
14 n->n_str = NULL;
Guido van Rossum3f5da241990-12-20 15:06:42 +000015 n->n_lineno = 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000016 n->n_nchildren = 0;
17 n->n_child = NULL;
18 return n;
19}
20
Tim Peters623fdb92002-07-08 19:11:07 +000021/* See comments at XXXROUNDUP below. Returns -1 on overflow. */
Tim Peters755ebea2002-07-08 06:32:09 +000022static int
23fancy_roundup(int n)
24{
25 /* Round up to the closest power of 2 >= n. */
26 int result = 256;
27 assert(n > 128);
Tim Peters623fdb92002-07-08 19:11:07 +000028 while (result < n) {
Tim Peters755ebea2002-07-08 06:32:09 +000029 result <<= 1;
Tim Peters623fdb92002-07-08 19:11:07 +000030 if (result <= 0)
31 return -1;
32 }
Tim Peters755ebea2002-07-08 06:32:09 +000033 return result;
34}
35
36/* A gimmick to make massive numbers of reallocs quicker. The result is
Tim Peterse561dc22002-07-15 17:58:03 +000037 * 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
Tim Peters755ebea2002-07-08 06:32:09 +000059 * 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).
Tim Peterse561dc22002-07-15 17:58:03 +000063 *
64 * In a run of compileall across the 2.3a0 Lib directory, Andrew MacIntyre
Neal Norwitz2c4e4f92006-04-10 06:42:25 +000065 * reported that, with this scheme, 89% of PyObject_REALLOC calls in
Tim Peterse561dc22002-07-15 17:58:03 +000066 * 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
Andrew M. Kuchling12ca69b2006-06-06 17:10:41 +000068 * platform-realloc disasters on vulnerable platforms.
Tim Peterse561dc22002-07-15 17:58:03 +000069 *
70 * Note that this would be straightforward if a node stored its current
71 * capacity. The code is tricky to avoid that.
Tim Peters755ebea2002-07-08 06:32:09 +000072 */
Tim Peterse561dc22002-07-15 17:58:03 +000073#define XXXROUNDUP(n) ((n) <= 1 ? (n) : \
74 (n) <= 128 ? (((n) + 3) & ~3) : \
Tim Peters755ebea2002-07-08 06:32:09 +000075 fancy_roundup(n))
76
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000077
Jeremy Hylton94988062000-06-20 19:10:44 +000078int
Martin v. Löwis49c5da12006-03-01 22:49:05 +000079PyNode_AddChild(register node *n1, int type, char *str, int lineno, int col_offset)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000080{
Tim Peters755ebea2002-07-08 06:32:09 +000081 const int nch = n1->n_nchildren;
82 int current_capacity;
83 int required_capacity;
84 node *n;
85
Fred Drakeef8ace32000-08-24 00:32:09 +000086 if (nch == INT_MAX || nch < 0)
Jeremy Hylton94988062000-06-20 19:10:44 +000087 return E_OVERFLOW;
Tim Peters755ebea2002-07-08 06:32:09 +000088
89 current_capacity = XXXROUNDUP(nch);
90 required_capacity = XXXROUNDUP(nch + 1);
Tim Peters623fdb92002-07-08 19:11:07 +000091 if (current_capacity < 0 || required_capacity < 0)
92 return E_OVERFLOW;
Tim Peters755ebea2002-07-08 06:32:09 +000093 if (current_capacity < required_capacity) {
Gregory P. Smith9d534572008-06-11 07:41:16 +000094 if (required_capacity > PY_SIZE_MAX / sizeof(node)) {
95 return E_NOMEM;
96 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000097 n = n1->n_child;
Andrew MacIntyre80d4e2a2002-08-04 06:28:21 +000098 n = (node *) PyObject_REALLOC(n,
99 required_capacity * sizeof(node));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000100 if (n == NULL)
Jeremy Hylton94988062000-06-20 19:10:44 +0000101 return E_NOMEM;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000102 n1->n_child = n;
103 }
Tim Peters755ebea2002-07-08 06:32:09 +0000104
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000105 n = &n1->n_child[n1->n_nchildren++];
106 n->n_type = type;
107 n->n_str = str;
Guido van Rossum3f5da241990-12-20 15:06:42 +0000108 n->n_lineno = lineno;
Martin v. Löwis49c5da12006-03-01 22:49:05 +0000109 n->n_col_offset = col_offset;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000110 n->n_nchildren = 0;
111 n->n_child = NULL;
Jeremy Hylton94988062000-06-20 19:10:44 +0000112 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000113}
Guido van Rossum03a24cd1990-11-18 17:37:06 +0000114
Guido van Rossum3f5da241990-12-20 15:06:42 +0000115/* Forward */
Tim Petersdbd9ba62000-07-09 03:09:57 +0000116static void freechildren(node *);
Guido van Rossum3f5da241990-12-20 15:06:42 +0000117
118
119void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000120PyNode_Free(node *n)
Guido van Rossum3f5da241990-12-20 15:06:42 +0000121{
122 if (n != NULL) {
123 freechildren(n);
Andrew MacIntyre80d4e2a2002-08-04 06:28:21 +0000124 PyObject_FREE(n);
Guido van Rossum3f5da241990-12-20 15:06:42 +0000125 }
126}
127
Guido van Rossum03a24cd1990-11-18 17:37:06 +0000128static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000129freechildren(node *n)
Guido van Rossum03a24cd1990-11-18 17:37:06 +0000130{
131 int i;
132 for (i = NCH(n); --i >= 0; )
133 freechildren(CHILD(n, i));
134 if (n->n_child != NULL)
Andrew MacIntyre80d4e2a2002-08-04 06:28:21 +0000135 PyObject_FREE(n->n_child);
Guido van Rossum03a24cd1990-11-18 17:37:06 +0000136 if (STR(n) != NULL)
Andrew MacIntyre80d4e2a2002-08-04 06:28:21 +0000137 PyObject_FREE(STR(n));
Guido van Rossum03a24cd1990-11-18 17:37:06 +0000138}