/* 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;

}