158e64a82eeec12711a55349f86ced990989a360bVladimir Marangozov/* Parse tree node implementation */ 258e64a82eeec12711a55349f86ced990989a360bVladimir Marangozov 31d6a7297d356d8daf84e3b29e029d2fc4d5f949fTim Peters#include "Python.h" 458e64a82eeec12711a55349f86ced990989a360bVladimir Marangozov#include "node.h" 558e64a82eeec12711a55349f86ced990989a360bVladimir Marangozov#include "errcode.h" 658e64a82eeec12711a55349f86ced990989a360bVladimir Marangozov 785a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossumnode * 823c9e0024af99379ae517b016b874d57127e9a97Thomas WoutersPyNode_New(int type) 985a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum{ 10c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou node *n = (node *) PyObject_MALLOC(1 * sizeof(node)); 11c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (n == NULL) 12c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 13c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_type = type; 14c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_str = NULL; 15c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_lineno = 0; 16c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_nchildren = 0; 17c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_child = NULL; 18c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return n; 1985a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum} 2085a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum 21623fdb9884bb1cf2f38036f0a5e81bccd6b78935Tim Peters/* See comments at XXXROUNDUP below. Returns -1 on overflow. */ 22755ebea23b8bac26661d3315ef68ccff61c55e6eTim Petersstatic int 23755ebea23b8bac26661d3315ef68ccff61c55e6eTim Petersfancy_roundup(int n) 24755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters{ 25c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* Round up to the closest power of 2 >= n. */ 26c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int result = 256; 27c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou assert(n > 128); 28c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou while (result < n) { 29c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou result <<= 1; 30c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (result <= 0) 31c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return -1; 32c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 33c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return result; 34755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters} 35755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters 36755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters/* A gimmick to make massive numbers of reallocs quicker. The result is 37e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * a number >= the input. In PyNode_AddChild, it's used like so, when 38e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * we're about to add child number current_size + 1: 39e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * 40e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * if XXXROUNDUP(current_size) < XXXROUNDUP(current_size + 1): 41e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * allocate space for XXXROUNDUP(current_size + 1) total children 42e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * else: 43e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * we already have enough space 44e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * 45e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * Since a node starts out empty, we must have 46e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * 47e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * XXXROUNDUP(0) < XXXROUNDUP(1) 48e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * 49e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * so that we allocate space for the first child. One-child nodes are very 50e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * common (presumably that would change if we used a more abstract form 51e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * of syntax tree), so to avoid wasting memory it's desirable that 52e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * XXXROUNDUP(1) == 1. That in turn forces XXXROUNDUP(0) == 0. 53e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * 54e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * Else for 2 <= n <= 128, we round up to the closest multiple of 4. Why 4? 55e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * Rounding up to a multiple of an exact power of 2 is very efficient, and 56e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * most nodes with more than one child have <= 4 kids. 57e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * 58e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * Else we call fancy_roundup() to grow proportionately to n. We've got an 59755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters * extreme case then (like test_longexp.py), and on many platforms doing 60755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters * anything less than proportional growth leads to exorbitant runtime 61755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters * (e.g., MacPython), or extreme fragmentation of user address space (e.g., 62755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters * Win98). 63e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * 64e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * In a run of compileall across the 2.3a0 Lib directory, Andrew MacIntyre 652c4e4f98397bcc591ad3a551e1e57cea0e2bd986Neal Norwitz * reported that, with this scheme, 89% of PyObject_REALLOC calls in 66e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * PyNode_AddChild passed 1 for the size, and 9% passed 4. So this usually 67e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * wastes very little memory, but is very effective at sidestepping 6812ca69bc0e42e799db52cfd0030c8b1d18049befAndrew M. Kuchling * platform-realloc disasters on vulnerable platforms. 69e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * 70e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * Note that this would be straightforward if a node stored its current 71e561dc231e31a304b69e66979fc9cc773b7668deTim Peters * capacity. The code is tricky to avoid that. 72755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters */ 73c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou#define XXXROUNDUP(n) ((n) <= 1 ? (n) : \ 74c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (n) <= 128 ? (((n) + 3) & ~3) : \ 75c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou fancy_roundup(n)) 76755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters 7785a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum 7894988067b96c6187fd940eaff99c2c5a68daac68Jeremy Hyltonint 7949c5da1d88f605248167f4d95b1dfe08c1f703c7Martin v. LöwisPyNode_AddChild(register node *n1, int type, char *str, int lineno, int col_offset) 8085a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum{ 81c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou const int nch = n1->n_nchildren; 82c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int current_capacity; 83c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int required_capacity; 84c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou node *n; 85755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters 86c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (nch == INT_MAX || nch < 0) 87c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return E_OVERFLOW; 88755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters 89c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou current_capacity = XXXROUNDUP(nch); 90c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou required_capacity = XXXROUNDUP(nch + 1); 91c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (current_capacity < 0 || required_capacity < 0) 92c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return E_OVERFLOW; 93c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (current_capacity < required_capacity) { 94c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (required_capacity > PY_SIZE_MAX / sizeof(node)) { 95c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return E_NOMEM; 96c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 97c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n = n1->n_child; 98c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n = (node *) PyObject_REALLOC(n, 99c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou required_capacity * sizeof(node)); 100c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (n == NULL) 101c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return E_NOMEM; 102c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n1->n_child = n; 103c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 104755ebea23b8bac26661d3315ef68ccff61c55e6eTim Peters 105c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n = &n1->n_child[n1->n_nchildren++]; 106c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_type = type; 107c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_str = str; 108c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_lineno = lineno; 109c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_col_offset = col_offset; 110c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_nchildren = 0; 111c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n->n_child = NULL; 112c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return 0; 11385a5fbbdfea617f6cc8fae82c9e8c2b5c424436dGuido van Rossum} 11403a24cd47b0d067110db1026e99e13e974409768Guido van Rossum 1153f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum/* Forward */ 116dbd9ba6a6c19c3d06f5684b3384a934f740038dbTim Petersstatic void freechildren(node *); 1173e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Ceastatic Py_ssize_t sizeofchildren(node *n); 1183f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum 1193f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum 1203f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossumvoid 12123c9e0024af99379ae517b016b874d57127e9a97Thomas WoutersPyNode_Free(node *n) 1223f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum{ 123c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (n != NULL) { 124c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou freechildren(n); 125c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_FREE(n); 126c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 1273f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum} 1283f5da24ea304e674a9abbdcffc4d671e32aa70f1Guido van Rossum 1293e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus CeaPy_ssize_t 1303e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea_PyNode_SizeOf(node *n) 1313e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea{ 1323e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea Py_ssize_t res = 0; 1333e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea 1343e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea if (n != NULL) 1353e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea res = sizeof(node) + sizeofchildren(n); 1363e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea return res; 1373e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea} 1383e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea 13903a24cd47b0d067110db1026e99e13e974409768Guido van Rossumstatic void 14023c9e0024af99379ae517b016b874d57127e9a97Thomas Woutersfreechildren(node *n) 14103a24cd47b0d067110db1026e99e13e974409768Guido van Rossum{ 142c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou int i; 143c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou for (i = NCH(n); --i >= 0; ) 144c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou freechildren(CHILD(n, i)); 145c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (n->n_child != NULL) 146c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_FREE(n->n_child); 147c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (STR(n) != NULL) 148c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_FREE(STR(n)); 14903a24cd47b0d067110db1026e99e13e974409768Guido van Rossum} 1503e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea 1513e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Ceastatic Py_ssize_t 1523e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Ceasizeofchildren(node *n) 1533e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea{ 1543e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea Py_ssize_t res = 0; 1553e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea int i; 1563e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea for (i = NCH(n); --i >= 0; ) 1573e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea res += sizeofchildren(CHILD(n, i)); 1583e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea if (n->n_child != NULL) 1593e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea /* allocated size of n->n_child array */ 1603e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea res += XXXROUNDUP(NCH(n)) * sizeof(node); 1613e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea if (STR(n) != NULL) 1623e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea res += strlen(STR(n)) + 1; 1633e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea return res; 1643e3192d8f76ca6bfbf111ed2059eaef8e49a53e5Jesus Cea} 165