/* Parse tree node implementation */

#include "Python.h"
#include "node.h"
#include "errcode.h"

node *
PyNode_New(int type)
{
 node *n = (node *) PyObject_MALLOC(1 * sizeof(node));
 if (n == NULL)
 return NULL;
 n->n_type = type;
 n->n_str = NULL;
 n->n_lineno = 0;
 n->n_end_lineno = 0;
 n->n_end_col_offset = -1;
 n->n_nchildren = 0;
 n->n_child = NULL;
 return n;
}

/* See comments at XXXROUNDUP below. Returns -1 on overflow. */
static int
fancy_roundup(int n)
{
 /* Round up to the closest power of 2 >= n. */
 int result = 256;
 assert(n > 128);
 while (result < n) {
 result <<= 1;
 if (result <= 0)
 return -1;
 }
 return result;
}

/* A gimmick to make massive numbers of reallocs quicker. The result is
 * a number >= the input. In PyNode_AddChild, it's used like so, when
 * we're about to add child number current_size + 1:
 *
 * if XXXROUNDUP(current_size) < XXXROUNDUP(current_size + 1):
 * allocate space for XXXROUNDUP(current_size + 1) total children
 * else:
 * we already have enough space
 *
 * Since a node starts out empty, we must have
 *
 * XXXROUNDUP(0) < XXXROUNDUP(1)
 *
 * so that we allocate space for the first child. One-child nodes are very
 * common (presumably that would change if we used a more abstract form
 * of syntax tree), so to avoid wasting memory it's desirable that
 * XXXROUNDUP(1) == 1. That in turn forces XXXROUNDUP(0) == 0.
 *
 * Else for 2 <= n <= 128, we round up to the closest multiple of 4. Why 4?
 * Rounding up to a multiple of an exact power of 2 is very efficient, and
 * most nodes with more than one child have <= 4 kids.
 *
 * Else we call fancy_roundup() to grow proportionately to n. We've got an
 * extreme case then (like test_longexp.py), and on many platforms doing
 * anything less than proportional growth leads to exorbitant runtime
 * (e.g., MacPython), or extreme fragmentation of user address space (e.g.,
 * Win98).
 *
 * In a run of compileall across the 2.3a0 Lib directory, Andrew MacIntyre
 * reported that, with this scheme, 89% of PyObject_REALLOC calls in
 * PyNode_AddChild passed 1 for the size, and 9% passed 4. So this usually
 * wastes very little memory, but is very effective at sidestepping
 * platform-realloc disasters on vulnerable platforms.
 *
 * Note that this would be straightforward if a node stored its current
 * capacity. The code is tricky to avoid that.
 */
#define XXXROUNDUP(n) ((n) <= 1 ? (n) : \
 (n) <= 128 ? (int)_Py_SIZE_ROUND_UP((n), 4) : \
 fancy_roundup(n))


void
_PyNode_FinalizeEndPos(node *n)
{
 int nch = NCH(n);
 node *last;
 if (nch == 0) {
 return;
 }
 last = CHILD(n, nch - 1);
 _PyNode_FinalizeEndPos(last);
 n->n_end_lineno = last->n_end_lineno;
 n->n_end_col_offset = last->n_end_col_offset;
}

int
PyNode_AddChild(node *n1, int type, char *str, int lineno, int col_offset,
 int end_lineno, int end_col_offset)
{
 const int nch = n1->n_nchildren;
 int current_capacity;
 int required_capacity;
 node *n;

 // finalize end position of previous node (if any)
 if (nch > 0) {
 _PyNode_FinalizeEndPos(CHILD(n1, nch - 1));
 }

 if (nch == INT_MAX || nch < 0)
 return E_OVERFLOW;

 current_capacity = XXXROUNDUP(nch);
 required_capacity = XXXROUNDUP(nch + 1);
 if (current_capacity < 0 || required_capacity < 0)
 return E_OVERFLOW;
 if (current_capacity < required_capacity) {
 if ((size_t)required_capacity > SIZE_MAX / sizeof(node)) {
 return E_NOMEM;
 }
 n = n1->n_child;
 n = (node *) PyObject_REALLOC(n,
 required_capacity * sizeof(node));
 if (n == NULL)
 return E_NOMEM;
 n1->n_child = n;
 }

 n = &n1->n_child[n1->n_nchildren++];
 n->n_type = type;
 n->n_str = str;
 n->n_lineno = lineno;
 n->n_col_offset = col_offset;
 n->n_end_lineno = end_lineno; // this and below will be updates after all children are added.
 n->n_end_col_offset = end_col_offset;
 n->n_nchildren = 0;
 n->n_child = NULL;
 return 0;
}

/* Forward */
static void freechildren(node *);
static Py_ssize_t sizeofchildren(node *n);


void
PyNode_Free(node *n)
{
 if (n != NULL) {
 freechildren(n);
 PyObject_FREE(n);
 }
}

Py_ssize_t
_PyNode_SizeOf(node *n)
{
 Py_ssize_t res = 0;

 if (n != NULL)
 res = sizeof(node) + sizeofchildren(n);
 return res;
}

static void
freechildren(node *n)
{
 int i;
 for (i = NCH(n); --i >= 0; )
 freechildren(CHILD(n, i));
 if (n->n_child != NULL)
 PyObject_FREE(n->n_child);
 if (STR(n) != NULL)
 PyObject_FREE(STR(n));
}

static Py_ssize_t
sizeofchildren(node *n)
{
 Py_ssize_t res = 0;
 int i;
 for (i = NCH(n); --i >= 0; )
 res += sizeofchildren(CHILD(n, i));
 if (n->n_child != NULL)
 /* allocated size of n->n_child array */
 res += XXXROUNDUP(NCH(n)) * sizeof(node);
 if (STR(n) != NULL)
 res += strlen(STR(n)) + 1;
 return res;
}