/*

 * ElementTree

 * $Id: _elementtree.c 2657 2006-03-12 20:50:32Z fredrik $

 *

 * elementtree accelerator

 *

 * History:

 * 1999-06-20 fl  created (as part of sgmlop)

 * 2001-05-29 fl  effdom edition

 * 2001-06-05 fl  backported to unix; fixed bogus free in clear

 * 2001-07-10 fl  added findall helper

 * 2003-02-27 fl  elementtree edition (alpha)

 * 2004-06-03 fl  updates for elementtree 1.2

 * 2005-01-05 fl  added universal name cache, Element/SubElement factories

 * 2005-01-06 fl  moved python helpers into C module; removed 1.5.2 support

 * 2005-01-07 fl  added 2.1 support; work around broken __copy__ in 2.3

 * 2005-01-08 fl  added makeelement method; fixed path support

 * 2005-01-10 fl  optimized memory usage

 * 2005-01-11 fl  first public release (cElementTree 0.8)

 * 2005-01-12 fl  split element object into base and extras

 * 2005-01-13 fl  use tagged pointers for tail/text (cElementTree 0.9)

 * 2005-01-17 fl  added treebuilder close method

 * 2005-01-17 fl  fixed crash in getchildren

 * 2005-01-18 fl  removed observer api, added iterparse (cElementTree 0.9.3)

 * 2005-01-23 fl  revised iterparse api; added namespace event support (0.9.8)

 * 2005-01-26 fl  added VERSION module property (cElementTree 1.0)

 * 2005-01-28 fl  added remove method (1.0.1)

 * 2005-03-01 fl  added iselement function; fixed makeelement aliasing (1.0.2)

 * 2005-03-13 fl  export Comment and ProcessingInstruction/PI helpers

 * 2005-03-26 fl  added Comment and PI support to XMLParser

 * 2005-03-27 fl  event optimizations; complain about bogus events

 * 2005-08-08 fl  fixed read error handling in parse

 * 2005-08-11 fl  added runtime test for copy workaround (1.0.3)

 * 2005-12-13 fl  added expat_capi support (for xml.etree) (1.0.4)

 * 2005-12-16 fl  added support for non-standard encodings

 * 2006-03-08 fl  fixed a couple of potential null-refs and leaks

 * 2006-03-12 fl  merge in 2.5 ssize_t changes

 *

 * Copyright (c) 1999-2006 by Secret Labs AB.  All rights reserved.

 * Copyright (c) 1999-2006 by Fredrik Lundh.

 *

 * info@pythonware.com

 * http://www.pythonware.com

 */

/* Licensed to PSF under a Contributor Agreement. */

/* See http://www.python.org/2.4/license for licensing details. */

#include "Python.h"

#define VERSION "1.0.6"

/* -------------------------------------------------------------------- */

/* configuration */

/* Leave defined to include the expat-based XMLParser type */

#define USE_EXPAT

/* Define to to all expat calls via pyexpat's embedded expat library */

/* #define USE_PYEXPAT_CAPI */

/* An element can hold this many children without extra memory

   allocations. */

#define STATIC_CHILDREN 4

/* For best performance, chose a value so that 80-90% of all nodes

   have no more than the given number of children.  Set this to zero

   to minimize the size of the element structure itself (this only

   helps if you have lots of leaf nodes with attributes). */

/* Also note that pymalloc always allocates blocks in multiples of

   eight bytes.  For the current version of cElementTree, this means

   that the number of children should be an even number, at least on

   32-bit platforms. */

/* -------------------------------------------------------------------- */

#if 0

static int memory = 0;

#define ALLOC(size, comment)\

do { memory += size; printf("%8d - %s\n", memory, comment); } while (0)

#define RELEASE(size, comment)\

do { memory -= size; printf("%8d - %s\n", memory, comment); } while (0)

#else

#define ALLOC(size, comment)

#define RELEASE(size, comment)

#endif

/* compiler tweaks */

#if defined(_MSC_VER)

#define LOCAL(type) static __inline type __fastcall

#else

#define LOCAL(type) static type

#endif

/* compatibility macros */

#if (PY_VERSION_HEX < 0x02050000)

typedef int Py_ssize_t;

#define lenfunc inquiry

#endif

#if (PY_VERSION_HEX < 0x02040000)

#define PyDict_CheckExact PyDict_Check

#if (PY_VERSION_HEX < 0x02020000)

#define PyList_CheckExact PyList_Check

#define PyString_CheckExact PyString_Check

#if (PY_VERSION_HEX >= 0x01060000)

#define Py_USING_UNICODE /* always enabled for 2.0 and 2.1 */

#endif

#endif

#endif

#if !defined(Py_RETURN_NONE)

#define Py_RETURN_NONE return Py_INCREF(Py_None), Py_None

#endif

/* macros used to store 'join' flags in string object pointers.  note

   that all use of text and tail as object pointers must be wrapped in

   JOIN_OBJ.  see comments in the ElementObject definition for more

   info. */

#define JOIN_GET(p) ((Py_uintptr_t) (p) & 1)

#define JOIN_SET(p, flag) ((void*) ((Py_uintptr_t) (JOIN_OBJ(p)) | (flag)))

#define JOIN_OBJ(p) ((PyObject*) ((Py_uintptr_t) (p) & ~1))

/* glue functions (see the init function for details) */

static PyObject* elementtree_copyelement_obj;

static PyObject* elementtree_deepcopy_obj;

static PyObject* elementtree_getiterator_obj;

static PyObject* elementpath_obj;

/* helpers */

LOCAL(PyObject*)

deepcopy(PyObject* object, PyObject* memo)

{

    /* do a deep copy of the given object */

    PyObject* args;

    PyObject* result;

    if (!elementtree_deepcopy_obj) {

        PyErr_SetString(

            PyExc_RuntimeError,

            "deepcopy helper not found"

            );

        return NULL;

    }

    args = PyTuple_New(2);

    if (!args)

        return NULL;

    Py_INCREF(object); PyTuple_SET_ITEM(args, 0, (PyObject*) object);

    Py_INCREF(memo);   PyTuple_SET_ITEM(args, 1, (PyObject*) memo);

    result = PyObject_CallObject(elementtree_deepcopy_obj, args);

    Py_DECREF(args);

    return result;

}

LOCAL(PyObject*)

list_join(PyObject* list)

{

    /* join list elements (destroying the list in the process) */

    PyObject* joiner;

    PyObject* function;

    PyObject* args;

    PyObject* result;

    switch (PyList_GET_SIZE(list)) {

    case 0:

        Py_DECREF(list);

        return PyString_FromString("");

    case 1:

        result = PyList_GET_ITEM(list, 0);

        Py_INCREF(result);

        Py_DECREF(list);

        return result;

    }

    /* two or more elements: slice out a suitable separator from the

       first member, and use that to join the entire list */

    joiner = PySequence_GetSlice(PyList_GET_ITEM(list, 0), 0, 0);

    if (!joiner)

        return NULL;

    function = PyObject_GetAttrString(joiner, "join");

    if (!function) {

        Py_DECREF(joiner);

        return NULL;

    }

    args = PyTuple_New(1);

    if (!args)

        return NULL;

    PyTuple_SET_ITEM(args, 0, list);

    result = PyObject_CallObject(function, args);

    Py_DECREF(args); /* also removes list */

    Py_DECREF(function);

    Py_DECREF(joiner);

    return result;

}

#if (PY_VERSION_HEX < 0x02020000)

LOCAL(int)

PyDict_Update(PyObject* dict, PyObject* other)

{

    /* PyDict_Update emulation for 2.1 and earlier */

    PyObject* res;

    res = PyObject_CallMethod(dict, "update", "O", other);

    if (!res)

        return -1;

    Py_DECREF(res);

    return 0;

}

#endif

/* -------------------------------------------------------------------- */

/* the element type */

typedef struct {

    /* attributes (a dictionary object), or None if no attributes */

    PyObject* attrib;

    /* child elements */

    int length; /* actual number of items */

    int allocated; /* allocated items */

    /* this either points to _children or to a malloced buffer */

    PyObject* *children;

    PyObject* _children[STATIC_CHILDREN];

} ElementObjectExtra;

typedef struct {

    PyObject_HEAD

    /* element tag (a string). */

    PyObject* tag;

    /* text before first child.  note that this is a tagged pointer;

       use JOIN_OBJ to get the object pointer.  the join flag is used

       to distinguish lists created by the tree builder from lists

       assigned to the attribute by application code; the former

       should be joined before being returned to the user, the latter

       should be left intact. */

    PyObject* text;

    /* text after this element, in parent.  note that this is a tagged

       pointer; use JOIN_OBJ to get the object pointer. */

    PyObject* tail;

    ElementObjectExtra* extra;

} ElementObject;

staticforward PyTypeObject Element_Type;

#define Element_CheckExact(op) (Py_TYPE(op) == &Element_Type)

/* -------------------------------------------------------------------- */

/* element constructor and destructor */

LOCAL(int)

element_new_extra(ElementObject* self, PyObject* attrib)

{

    self->extra = PyObject_Malloc(sizeof(ElementObjectExtra));

    if (!self->extra)

        return -1;

    if (!attrib)

        attrib = Py_None;

    Py_INCREF(attrib);

    self->extra->attrib = attrib;

    self->extra->length = 0;

    self->extra->allocated = STATIC_CHILDREN;

    self->extra->children = self->extra->_children;

    return 0;

}

LOCAL(void)

element_dealloc_extra(ElementObject* self)

{

    int i;

    Py_DECREF(self->extra->attrib);

    for (i = 0; i < self->extra->length; i++)

        Py_DECREF(self->extra->children[i]);

    if (self->extra->children != self->extra->_children)

        PyObject_Free(self->extra->children);

    PyObject_Free(self->extra);

}

LOCAL(PyObject*)

element_new(PyObject* tag, PyObject* attrib)

{

    ElementObject* self;

    self = PyObject_New(ElementObject, &Element_Type);

    if (self == NULL)

        return NULL;

    /* use None for empty dictionaries */

    if (PyDict_CheckExact(attrib) && !PyDict_Size(attrib))

        attrib = Py_None;

    self->extra = NULL;

    if (attrib != Py_None) {

        if (element_new_extra(self, attrib) < 0) {

            PyObject_Del(self);

            return NULL;

	}

        self->extra->length = 0;

        self->extra->allocated = STATIC_CHILDREN;

        self->extra->children = self->extra->_children;

    }

    Py_INCREF(tag);

    self->tag = tag;

    Py_INCREF(Py_None);

    self->text = Py_None;

    Py_INCREF(Py_None);

    self->tail = Py_None;

    ALLOC(sizeof(ElementObject), "create element");

    return (PyObject*) self;

}

LOCAL(int)

element_resize(ElementObject* self, int extra)

{

    int size;

    PyObject* *children;

    /* make sure self->children can hold the given number of extra

       elements.  set an exception and return -1 if allocation failed */

    if (!self->extra)

        element_new_extra(self, NULL);

    size = self->extra->length + extra;

    if (size > self->extra->allocated) {

        /* use Python 2.4's list growth strategy */

        size = (size >> 3) + (size < 9 ? 3 : 6) + size;

        /* Coverity CID #182 size_error: Allocating 1 bytes to pointer "children"

         * which needs at least 4 bytes. 

         * Although it's a false alarm always assume at least one child to 

         * be safe.

         */

        size = size ? size : 1;

        if (self->extra->children != self->extra->_children) {

            /* Coverity CID #182 size_error: Allocating 1 bytes to pointer

             * "children", which needs at least 4 bytes. Although it's a 

             * false alarm always assume at least one child to be safe.

             */

            children = PyObject_Realloc(self->extra->children,

                                        size * sizeof(PyObject*));

            if (!children)

                goto nomemory;

        } else {

            children = PyObject_Malloc(size * sizeof(PyObject*));

            if (!children)

                goto nomemory;

            /* copy existing children from static area to malloc buffer */

            memcpy(children, self->extra->children,

                   self->extra->length * sizeof(PyObject*));

        }

        self->extra->children = children;

        self->extra->allocated = size;

    }

    return 0;

  nomemory:

    PyErr_NoMemory();

    return -1;

}

LOCAL(int)

element_add_subelement(ElementObject* self, PyObject* element)

{

    /* add a child element to a parent */

    if (element_resize(self, 1) < 0)

        return -1;

    Py_INCREF(element);

    self->extra->children[self->extra->length] = element;

    self->extra->length++;

    return 0;

}

LOCAL(PyObject*)

element_get_attrib(ElementObject* self)

{

    /* return borrowed reference to attrib dictionary */

    /* note: this function assumes that the extra section exists */

    PyObject* res = self->extra->attrib;

    if (res == Py_None) {

        /* create missing dictionary */

        res = PyDict_New();

        if (!res)

            return NULL;

        self->extra->attrib = res;

    }

    return res;

}

LOCAL(PyObject*)

element_get_text(ElementObject* self)

{

    /* return borrowed reference to text attribute */

    PyObject* res = self->text;

    if (JOIN_GET(res)) {

        res = JOIN_OBJ(res);

        if (PyList_CheckExact(res)) {

            res = list_join(res);

            if (!res)

                return NULL;

            self->text = res;

        }

    }

    return res;

}

LOCAL(PyObject*)

element_get_tail(ElementObject* self)

{

    /* return borrowed reference to text attribute */

    PyObject* res = self->tail;

    if (JOIN_GET(res)) {

        res = JOIN_OBJ(res);

        if (PyList_CheckExact(res)) {

            res = list_join(res);

            if (!res)

                return NULL;

            self->tail = res;

        }

    }

    return res;

}

static PyObject*

element(PyObject* self, PyObject* args, PyObject* kw)

{

    PyObject* elem;

    PyObject* tag;

    PyObject* attrib = NULL;

    if (!PyArg_ParseTuple(args, "O|O!:Element", &tag,

                          &PyDict_Type, &attrib))

        return NULL;

    if (attrib || kw) {

        attrib = (attrib) ? PyDict_Copy(attrib) : PyDict_New();

        if (!attrib)

            return NULL;

        if (kw)

            PyDict_Update(attrib, kw);

    } else {

        Py_INCREF(Py_None);

        attrib = Py_None;

    }

    elem = element_new(tag, attrib);

    Py_DECREF(attrib);

    return elem;

}

static PyObject*

subelement(PyObject* self, PyObject* args, PyObject* kw)

{

    PyObject* elem;

    ElementObject* parent;

    PyObject* tag;

    PyObject* attrib = NULL;

    if (!PyArg_ParseTuple(args, "O!O|O!:SubElement",

                          &Element_Type, &parent, &tag,

                          &PyDict_Type, &attrib))

        return NULL;

    if (attrib || kw) {

        attrib = (attrib) ? PyDict_Copy(attrib) : PyDict_New();

        if (!attrib)

            return NULL;

        if (kw)

            PyDict_Update(attrib, kw);

    } else {