1 /*

     2  * ElementTree

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

     4  *

     5  * elementtree accelerator

     6  *

     7  * History:

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

     9  * 2001-05-29 fl  effdom edition

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

    11  * 2001-07-10 fl  added findall helper

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

    13  * 2004-06-03 fl  updates for elementtree 1.2

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

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

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

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

    18  * 2005-01-10 fl  optimized memory usage

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

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

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

    22  * 2005-01-17 fl  added treebuilder close method

    23  * 2005-01-17 fl  fixed crash in getchildren

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    38  *

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

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

    41  *

    42  * info@pythonware.com

    43  * http://www.pythonware.com

    44  */

    45 

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

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

    48 

    49 #include "Python.h"

    50 

    51 #define VERSION "1.0.6"

    52 

    53 /* -------------------------------------------------------------------- */

    54 /* configuration */

    55 

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

    57 #define USE_EXPAT

    58 

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

    60 /* #define USE_PYEXPAT_CAPI */

    61 

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

    63    allocations. */

    64 #define STATIC_CHILDREN 4

    65 

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

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

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

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

    70 

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

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

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

    74    32-bit platforms. */

    75 

    76 /* -------------------------------------------------------------------- */

    77 

    78 #if 0

    79 static int memory = 0;

    80 #define ALLOC(size, comment)\

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

    82 #define RELEASE(size, comment)\

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

    84 #else

    85 #define ALLOC(size, comment)

    86 #define RELEASE(size, comment)

    87 #endif

    88 

    89 /* compiler tweaks */

    90 #if defined(_MSC_VER)

    91 #define LOCAL(type) static __inline type __fastcall

    92 #else

    93 #define LOCAL(type) static type

    94 #endif

    95 

    96 /* compatibility macros */

    97 #if (PY_VERSION_HEX < 0x02050000)

    98 typedef int Py_ssize_t;

    99 #define lenfunc inquiry

   100 #endif

   101 

   102 #if (PY_VERSION_HEX < 0x02040000)

   103 #define PyDict_CheckExact PyDict_Check

   104 #if (PY_VERSION_HEX < 0x02020000)

   105 #define PyList_CheckExact PyList_Check

   106 #define PyString_CheckExact PyString_Check

   107 #if (PY_VERSION_HEX >= 0x01060000)

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

   109 #endif

   110 #endif

   111 #endif

   112 

   113 #if !defined(Py_RETURN_NONE)

   114 #define Py_RETURN_NONE return Py_INCREF(Py_None), Py_None

   115 #endif

   116 

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

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

   119    JOIN_OBJ.  see comments in the ElementObject definition for more

   120    info. */

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

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

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

   124 

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

   126 static PyObject* elementtree_copyelement_obj;

   127 static PyObject* elementtree_deepcopy_obj;

   128 static PyObject* elementtree_getiterator_obj;

   129 static PyObject* elementpath_obj;

   130 

   131 /* helpers */

   132 

   133 LOCAL(PyObject*)

   134 deepcopy(PyObject* object, PyObject* memo)

   135 {

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

   137 

   138     PyObject* args;

   139     PyObject* result;

   140 

   141     if (!elementtree_deepcopy_obj) {

   142         PyErr_SetString(

   143             PyExc_RuntimeError,

   144             "deepcopy helper not found"

   145             );

   146         return NULL;

   147     }

   148 

   149     args = PyTuple_New(2);

   150     if (!args)

   151         return NULL;

   152 

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

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

   155 

   156     result = PyObject_CallObject(elementtree_deepcopy_obj, args);

   157 

   158     Py_DECREF(args);

   159 

   160     return result;

   161 }

   162 

   163 LOCAL(PyObject*)

   164 list_join(PyObject* list)

   165 {

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

   167 

   168     PyObject* joiner;

   169     PyObject* function;

   170     PyObject* args;

   171     PyObject* result;

   172 

   173     switch (PyList_GET_SIZE(list)) {

   174     case 0:

   175         Py_DECREF(list);

   176         return PyString_FromString("");

   177     case 1:

   178         result = PyList_GET_ITEM(list, 0);

   179         Py_INCREF(result);

   180         Py_DECREF(list);

   181         return result;

   182     }

   183 

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

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

   186 

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

   188     if (!joiner)

   189         return NULL;

   190 

   191     function = PyObject_GetAttrString(joiner, "join");

   192     if (!function) {

   193         Py_DECREF(joiner);

   194         return NULL;

   195     }

   196 

   197     args = PyTuple_New(1);

   198     if (!args)

   199         return NULL;

   200 

   201     PyTuple_SET_ITEM(args, 0, list);

   202 

   203     result = PyObject_CallObject(function, args);

   204 

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

   206     Py_DECREF(function);

   207     Py_DECREF(joiner);

   208 

   209     return result;

   210 }

   211 

   212 #if (PY_VERSION_HEX < 0x02020000)

   213 LOCAL(int)

   214 PyDict_Update(PyObject* dict, PyObject* other)

   215 {

   216     /* PyDict_Update emulation for 2.1 and earlier */

   217 

   218     PyObject* res;

   219     

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

   221     if (!res)

   222         return -1;

   223 

   224     Py_DECREF(res);

   225     return 0;

   226 }

   227 #endif

   228 

   229 /* -------------------------------------------------------------------- */

   230 /* the element type */

   231 

   232 typedef struct {

   233 

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

   235     PyObject* attrib;

   236 

   237     /* child elements */

   238     int length; /* actual number of items */

   239     int allocated; /* allocated items */

   240 

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

   242     PyObject* *children;

   243 

   244     PyObject* _children[STATIC_CHILDREN];

   245     

   246 } ElementObjectExtra;

   247 

   248 typedef struct {

   249     PyObject_HEAD

   250 

   251     /* element tag (a string). */

   252     PyObject* tag;

   253 

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

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

   256        to distinguish lists created by the tree builder from lists

   257        assigned to the attribute by application code; the former

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

   259        should be left intact. */

   260     PyObject* text;

   261 

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

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

   264     PyObject* tail;

   265 

   266     ElementObjectExtra* extra;

   267 

   268 } ElementObject;

   269 

   270 staticforward PyTypeObject Element_Type;

   271 

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

   273 

   274 /* -------------------------------------------------------------------- */

   275 /* element constructor and destructor */

   276 

   277 LOCAL(int)

   278 element_new_extra(ElementObject* self, PyObject* attrib)

   279 {

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

   281     if (!self->extra)

   282         return -1;

   283 

   284     if (!attrib)

   285         attrib = Py_None;

   286 

   287     Py_INCREF(attrib);

   288     self->extra->attrib = attrib;

   289 

   290     self->extra->length = 0;

   291     self->extra->allocated = STATIC_CHILDREN;

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

   293 

   294     return 0;

   295 }

   296 

   297 LOCAL(void)

   298 element_dealloc_extra(ElementObject* self)

   299 {

   300     int i;

   301 

   302     Py_DECREF(self->extra->attrib);

   303 

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

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

   306 

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

   308         PyObject_Free(self->extra->children);

   309 

   310     PyObject_Free(self->extra);

   311 }

   312 

   313 LOCAL(PyObject*)

   314 element_new(PyObject* tag, PyObject* attrib)

   315 {

   316     ElementObject* self;

   317 

   318     self = PyObject_New(ElementObject, &Element_Type);

   319     if (self == NULL)

   320         return NULL;

   321 

   322     /* use None for empty dictionaries */

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

   324         attrib = Py_None;

   325 

   326     self->extra = NULL;

   327 

   328     if (attrib != Py_None) {

   329 

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

   331             PyObject_Del(self);

   332             return NULL;

   333 	}

   334 

   335         self->extra->length = 0;

   336         self->extra->allocated = STATIC_CHILDREN;

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

   338 

   339     }

   340 

   341     Py_INCREF(tag);

   342     self->tag = tag;

   343 

   344     Py_INCREF(Py_None);

   345     self->text = Py_None;

   346 

   347     Py_INCREF(Py_None);

   348     self->tail = Py_None;

   349 

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

   351 

   352     return (PyObject*) self;

   353 }

   354 

   355 LOCAL(int)

   356 element_resize(ElementObject* self, int extra)

   357 {

   358     int size;

   359     PyObject* *children;

   360 

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

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

   363 

   364     if (!self->extra)

   365         element_new_extra(self, NULL);

   366 

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

   368 

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

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

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

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

   373          * which needs at least 4 bytes. 

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

   375          * be safe.

   376          */

   377         size = size ? size : 1;

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

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

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

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

   382              */

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

   384                                         size * sizeof(PyObject*));

   385             if (!children)

   386                 goto nomemory;

   387         } else {

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

   389             if (!children)

   390                 goto nomemory;

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

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

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

   394         }

   395         self->extra->children = children;

   396         self->extra->allocated = size;

   397     }

   398 

   399     return 0;

   400 

   401   nomemory:

   402     PyErr_NoMemory();

   403     return -1;

   404 }

   405 

   406 LOCAL(int)

   407 element_add_subelement(ElementObject* self, PyObject* element)

   408 {

   409     /* add a child element to a parent */

   410 

   411     if (element_resize(self, 1) < 0)

   412         return -1;

   413 

   414     Py_INCREF(element);

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

   416 

   417     self->extra->length++;

   418 

   419     return 0;

   420 }

   421 

   422 LOCAL(PyObject*)

   423 element_get_attrib(ElementObject* self)

   424 {

   425     /* return borrowed reference to attrib dictionary */

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

   427 

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

   429 

   430     if (res == Py_None) {

   431         /* create missing dictionary */

   432         res = PyDict_New();

   433         if (!res)

   434             return NULL;

   435         self->extra->attrib = res;

   436     }

   437 

   438     return res;

   439 }

   440 

   441 LOCAL(PyObject*)

   442 element_get_text(ElementObject* self)

   443 {

   444     /* return borrowed reference to text attribute */

   445 

   446     PyObject* res = self->text;

   447 

   448     if (JOIN_GET(res)) {

   449         res = JOIN_OBJ(res);

   450         if (PyList_CheckExact(res)) {

   451             res = list_join(res);

   452             if (!res)

   453                 return NULL;

   454             self->text = res;

   455         }

   456     }

   457 

   458     return res;

   459 }

   460 

   461 LOCAL(PyObject*)

   462 element_get_tail(ElementObject* self)

   463 {

   464     /* return borrowed reference to text attribute */

   465 

   466     PyObject* res = self->tail;

   467 

   468     if (JOIN_GET(res)) {

   469         res = JOIN_OBJ(res);

   470         if (PyList_CheckExact(res)) {

   471             res = list_join(res);

   472             if (!res)

   473                 return NULL;

   474             self->tail = res;

   475         }

   476     }

   477 

   478     return res;

   479 }

   480 

   481 static PyObject*

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

   483 {

   484     PyObject* elem;

   485 

   486     PyObject* tag;

   487     PyObject* attrib = NULL;

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

   489                           &PyDict_Type, &attrib))

   490         return NULL;

   491 

   492     if (attrib || kw) {

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

   494         if (!attrib)

   495             return NULL;

   496         if (kw)

   497             PyDict_Update(attrib, kw);

   498     } else {

   499         Py_INCREF(Py_None);

   500         attrib = Py_None;

   501     }

   502 

   503     elem = element_new(tag, attrib);

   504 

   505     Py_DECREF(attrib);

   506 

   507     return elem;

   508 }

   509 

   510 static PyObject*

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

   512 {

   513     PyObject* elem;

   514 

   515     ElementObject* parent;

   516     PyObject* tag;

   517     PyObject* attrib = NULL;

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

   519                           &Element_Type, &parent, &tag,

   520                           &PyDict_Type, &attrib))

   521         return NULL;

   522 

   523     if (attrib || kw) {

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

   525         if (!attrib)

   526             return NULL;

   527         if (kw)

   528             PyDict_Update(attrib, kw);

   529     } else {

   530         Py_INCREF(Py_None);

   531         attrib = Py_None;

   532     }

   533 

   534     elem = element_new(tag, attrib);

   535 

   536     Py_DECREF(attrib);

   537 

   538     if (element_add_subelement(parent, elem) < 0) {

   539         Py_DECREF(elem);

   540         return NULL;

   541     }

   542 

   543     return elem;

   544 }

   545 

   546 static void

   547 element_dealloc(ElementObject* self)

   548 {

   549     if (self->extra)

   550         element_dealloc_extra(self);

   551 

   552     /* discard attributes */

   553     Py_DECREF(self->tag);

   554     Py_DECREF(JOIN_OBJ(self->text));

   555     Py_DECREF(JOIN_OBJ(self->tail));

   556 

   557     RELEASE(sizeof(ElementObject), "destroy element");

   558 

   559     PyObject_Del(self);

   560 }

   561 

   562 /* -------------------------------------------------------------------- */

   563 /* methods (in alphabetical order) */

   564 

   565 static PyObject*

   566 element_append(ElementObject* self, PyObject* args)

   567 {

   568     PyObject* element;

   569     if (!PyArg_ParseTuple(args, "O!:append", &Element_Type, &element))

   570         return NULL;

   571 

   572     if (element_add_subelement(self, element) < 0)

   573         return NULL;

   574 

   575     Py_RETURN_NONE;

   576 }

   577 

   578 static PyObject*

   579 element_clear(ElementObject* self, PyObject* args)

   580 {

   581     if (!PyArg_ParseTuple(args, ":clear"))

   582         return NULL;

   583 

   584     if (self->extra) {

   585         element_dealloc_extra(self);

   586         self->extra = NULL;

   587     }

   588 

   589     Py_INCREF(Py_None);

   590     Py_DECREF(JOIN_OBJ(self->text));

   591     self->text = Py_None;

   592 

   593     Py_INCREF(Py_None);

   594     Py_DECREF(JOIN_OBJ(self->tail));

   595     self->tail = Py_None;

   596 

   597     Py_RETURN_NONE;

   598 }

   599 

   600 static PyObject*

   601 element_copy(ElementObject* self, PyObject* args)

   602 {

   603     int i;

   604     ElementObject* element;

   605 

   606     if (!PyArg_ParseTuple(args, ":__copy__"))

   607         return NULL;

   608 

   609     element = (ElementObject*) element_new(

   610         self->tag, (self->extra) ? self->extra->attrib : Py_None

   611         );

   612     if (!element)

   613         return NULL;

   614 

   615     Py_DECREF(JOIN_OBJ(element->text));

   616     element->text = self->text;

   617     Py_INCREF(JOIN_OBJ(element->text));

   618 

   619     Py_DECREF(JOIN_OBJ(element->tail));

   620     element->tail = self->tail;

   621     Py_INCREF(JOIN_OBJ(element->tail));

   622 

   623     if (self->extra) {

   624         

   625         if (element_resize(element, self->extra->length) < 0) {

   626             Py_DECREF(element);

   627             return NULL;

   628         }

   629 

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

   631             Py_INCREF(self->extra->children[i]);

   632             element->extra->children[i] = self->extra->children[i];

   633         }

   634 

   635         element->extra->length = self->extra->length;

   636         

   637     }

   638 

   639     return (PyObject*) element;

   640 }

   641 

   642 static PyObject*

   643 element_deepcopy(ElementObject* self, PyObject* args)

   644 {

   645     int i;

   646     ElementObject* element;

   647     PyObject* tag;

   648     PyObject* attrib;

   649     PyObject* text;

   650     PyObject* tail;

   651     PyObject* id;

   652 

   653     PyObject* memo;

   654     if (!PyArg_ParseTuple(args, "O:__deepcopy__", &memo))

   655         return NULL;

   656 

   657     tag = deepcopy(self->tag, memo);

   658     if (!tag)

   659         return NULL;

   660 

   661     if (self->extra) {

   662         attrib = deepcopy(self->extra->attrib, memo);

   663         if (!attrib) {

   664             Py_DECREF(tag);

   665             return NULL;

   666         }

   667     } else {

   668         Py_INCREF(Py_None);

   669         attrib = Py_None;

   670     }

   671 

   672     element = (ElementObject*) element_new(tag, attrib);

   673 

   674     Py_DECREF(tag);

   675     Py_DECREF(attrib);

   676 

   677     if (!element)

   678         return NULL;

   679     

   680     text = deepcopy(JOIN_OBJ(self->text), memo);

   681     if (!text)

   682         goto error;

   683     Py_DECREF(element->text);

   684     element->text = JOIN_SET(text, JOIN_GET(self->text));

   685 

   686     tail = deepcopy(JOIN_OBJ(self->tail), memo);

   687     if (!tail)

   688         goto error;

   689     Py_DECREF(element->tail);

   690     element->tail = JOIN_SET(tail, JOIN_GET(self->tail));

   691 

   692     if (self->extra) {

   693         

   694         if (element_resize(element, self->extra->length) < 0)

   695             goto error;

   696 

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

   698             PyObject* child = deepcopy(self->extra->children[i], memo);

   699             if (!child) {

   700                 element->extra->length = i;

   701                 goto error;

   702             }

   703             element->extra->children[i] = child;

   704         }

   705 

   706         element->extra->length = self->extra->length;

   707         

   708     }

   709 

   710     /* add object to memo dictionary (so deepcopy won't visit it again) */

   711     id = PyInt_FromLong((Py_uintptr_t) self);

   712 

   713     i = PyDict_SetItem(memo, id, (PyObject*) element);

   714 

   715     Py_DECREF(id);

   716 

   717     if (i < 0)

   718         goto error;

   719 

   720     return (PyObject*) element;

   721 

   722   error:

   723     Py_DECREF(element);

   724     return NULL;

   725 }

   726 

   727 LOCAL(int)

   728 checkpath(PyObject* tag)

   729 {

   730     Py_ssize_t i;

   731     int check = 1;

   732 

   733     /* check if a tag contains an xpath character */

   734 

   735 #define PATHCHAR(ch) (ch == '/' || ch == '*' || ch == '[' || ch == '@')

   736 

   737 #if defined(Py_USING_UNICODE)

   738     if (PyUnicode_Check(tag)) {

   739         Py_UNICODE *p = PyUnicode_AS_UNICODE(tag);

   740         for (i = 0; i < PyUnicode_GET_SIZE(tag); i++) {

   741             if (p[i] == '{')

   742                 check = 0;

   743             else if (p[i] == '}')

   744                 check = 1;

   745             else if (check && PATHCHAR(p[i]))

   746                 return 1;

   747         }

   748         return 0;

   749     }

   750 #endif

   751     if (PyString_Check(tag)) {

   752         char *p = PyString_AS_STRING(tag);

   753         for (i = 0; i < PyString_GET_SIZE(tag); i++) {

   754             if (p[i] == '{')

   755                 check = 0;

   756             else if (p[i] == '}')

   757                 check = 1;

   758             else if (check && PATHCHAR(p[i]))

   759                 return 1;

   760         }

   761         return 0;

   762     }

   763 

   764     return 1; /* unknown type; might be path expression */

   765 }

   766 

   767 static PyObject*

   768 element_find(ElementObject* self, PyObject* args)

   769 {

   770     int i;

   771 

   772     PyObject* tag;

   773     if (!PyArg_ParseTuple(args, "O:find", &tag))

   774         return NULL;

   775 

   776     if (checkpath(tag))

   777         return PyObject_CallMethod(

   778             elementpath_obj, "find", "OO", self, tag

   779             );

   780 

   781     if (!self->extra)

   782         Py_RETURN_NONE;

   783         

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

   785         PyObject* item = self->extra->children[i];

   786         if (Element_CheckExact(item) &&

   787             PyObject_Compare(((ElementObject*)item)->tag, tag) == 0) {

   788             Py_INCREF(item);

   789             return item;

   790         }

   791     }

   792 

   793     Py_RETURN_NONE;

   794 }

   795 

   796 static PyObject*

   797 element_findtext(ElementObject* self, PyObject* args)

   798 {

   799     int i;

   800 

   801     PyObject* tag;

   802     PyObject* default_value = Py_None;

   803     if (!PyArg_ParseTuple(args, "O|O:findtext", &tag, &default_value))

   804         return NULL;

   805 

   806     if (checkpath(tag))

   807         return PyObject_CallMethod(

   808             elementpath_obj, "findtext", "OOO", self, tag, default_value

   809             );

   810 

   811     if (!self->extra) {

   812         Py_INCREF(default_value);

   813         return default_value;

   814     }

   815 

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

   817         ElementObject* item = (ElementObject*) self->extra->children[i];

   818         if (Element_CheckExact(item) && !PyObject_Compare(item->tag, tag)) {

   819             PyObject* text = element_get_text(item);

   820             if (text == Py_None)

   821                 return PyString_FromString("");

   822             Py_XINCREF(text);

   823             return text;

   824         }

   825     }

   826 

   827     Py_INCREF(default_value);

   828     return default_value;

   829 }

   830 

   831 static PyObject*

   832 element_findall(ElementObject* self, PyObject* args)

   833 {

   834     int i;

   835     PyObject* out;

   836 

   837     PyObject* tag;

   838     if (!PyArg_ParseTuple(args, "O:findall", &tag))

   839         return NULL;

   840 

   841     if (checkpath(tag))

   842         return PyObject_CallMethod(

   843             elementpath_obj, "findall", "OO", self, tag

   844             );

   845 

   846     out = PyList_New(0);

   847     if (!out)

   848         return NULL;

   849 

   850     if (!self->extra)

   851         return out;

   852 

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

   854         PyObject* item = self->extra->children[i];

   855         if (Element_CheckExact(item) &&

   856             PyObject_Compare(((ElementObject*)item)->tag, tag) == 0) {

   857             if (PyList_Append(out, item) < 0) {

   858                 Py_DECREF(out);

   859                 return NULL;

   860             }

   861         }

   862     }

   863 

   864     return out;

   865 }

   866 

   867 static PyObject*

   868 element_get(ElementObject* self, PyObject* args)

   869 {

   870     PyObject* value;

   871 

   872     PyObject* key;

   873     PyObject* default_value = Py_None;

   874     if (!PyArg_ParseTuple(args, "O|O:get", &key, &default_value))

   875         return NULL;

   876 

   877     if (!self->extra || self->extra->attrib == Py_None)

   878         value = default_value;

   879     else {

   880         value = PyDict_GetItem(self->extra->attrib, key);

   881         if (!value)

   882             value = default_value;

   883     }

   884 

   885     Py_INCREF(value);

   886     return value;

   887 }

   888 

   889 static PyObject*

   890 element_getchildren(ElementObject* self, PyObject* args)

   891 {

   892     int i;

   893     PyObject* list;

   894 

   895     if (!PyArg_ParseTuple(args, ":getchildren"))

   896         return NULL;

   897 

   898     if (!self->extra)

   899         return PyList_New(0);

   900 

   901     list = PyList_New(self->extra->length);

   902     if (!list)

   903         return NULL;

   904 

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

   906         PyObject* item = self->extra->children[i];

   907         Py_INCREF(item);

   908         PyList_SET_ITEM(list, i, item);

   909     }

   910 

   911     return list;

   912 }

   913 

   914 static PyObject*

   915 element_getiterator(ElementObject* self, PyObject* args)

   916 {

   917     PyObject* result;

   918     

   919     PyObject* tag = Py_None;

   920     if (!PyArg_ParseTuple(args, "|O:getiterator", &tag))

   921         return NULL;

   922 

   923     if (!elementtree_getiterator_obj) {

   924         PyErr_SetString(

   925             PyExc_RuntimeError,

   926             "getiterator helper not found"

   927             );

   928         return NULL;

   929     }

   930 

   931     args = PyTuple_New(2);

   932     if (!args)

   933         return NULL;

   934 

   935     Py_INCREF(self); PyTuple_SET_ITEM(args, 0, (PyObject*) self);

   936     Py_INCREF(tag);  PyTuple_SET_ITEM(args, 1, (PyObject*) tag);

   937 

   938     result = PyObject_CallObject(elementtree_getiterator_obj, args);

   939 

   940     Py_DECREF(args);

   941 

   942     return result;

   943 }

   944 

   945 static PyObject*

   946 element_getitem(PyObject* self_, Py_ssize_t index)

   947 {

   948     ElementObject* self = (ElementObject*) self_;

   949 

   950     if (!self->extra || index < 0 || index >= self->extra->length) {

   951         PyErr_SetString(

   952             PyExc_IndexError,

   953             "child index out of range"

   954             );

   955         return NULL;

   956     }

   957 

   958     Py_INCREF(self->extra->children[index]);

   959     return self->extra->children[index];

   960 }

   961 

   962 static PyObject*

   963 element_getslice(PyObject* self_, Py_ssize_t start, Py_ssize_t end)

   964 {

   965     ElementObject* self = (ElementObject*) self_;

   966     Py_ssize_t i;

   967     PyObject* list;

   968 

   969     if (!self->extra)

   970         return PyList_New(0);

   971 

   972     /* standard clamping */

   973     if (start < 0)

   974         start = 0;

   975     if (end < 0)

   976         end = 0;

   977     if (end > self->extra->length)

   978         end = self->extra->length;

   979     if (start > end)

   980         start = end;

   981 

   982     list = PyList_New(end - start);

   983     if (!list)

   984         return NULL;

   985 

   986     for (i = start; i < end; i++) {

   987         PyObject* item = self->extra->children[i];

   988         Py_INCREF(item);

   989         PyList_SET_ITEM(list, i - start, item);

   990     }

   991 

   992     return list;

   993 }

   994 

   995 static PyObject*

   996 element_insert(ElementObject* self, PyObject* args)

   997 {

   998     int i;

   999 

  1000     int index;

  1001     PyObject* element;

  1002     if (!PyArg_ParseTuple(args, "iO!:insert", &index,

  1003                           &Element_Type, &element))

  1004         return NULL;

  1005 

  1006     if (!self->extra)

  1007         element_new_extra(self, NULL);

  1008 

  1009     if (index < 0)

  1010         index = 0;

  1011     if (index > self->extra->length)

  1012         index = self->extra->length;

  1013 

  1014     if (element_resize(self, 1) < 0)

  1015         return NULL;

  1016 

  1017     for (i = self->extra->length; i > index; i--)

  1018         self->extra->children[i] = self->extra->children[i-1];

  1019 

  1020     Py_INCREF(element);

  1021     self->extra->children[index] = element;

  1022 

  1023     self->extra->length++;

  1024 

  1025     Py_RETURN_NONE;

  1026 }

  1027 

  1028 static PyObject*

  1029 element_items(ElementObject* self, PyObject* args)

  1030 {

  1031     if (!PyArg_ParseTuple(args, ":items"))

  1032         return NULL;

  1033 

  1034     if (!self->extra || self->extra->attrib == Py_None)

  1035         return PyList_New(0);

  1036 

  1037     return PyDict_Items(self->extra->attrib);

  1038 }

  1039 

  1040 static PyObject*

  1041 element_keys(ElementObject* self, PyObject* args)

  1042 {

  1043     if (!PyArg_ParseTuple(args, ":keys"))

  1044         return NULL;

  1045 

  1046     if (!self->extra || self->extra->attrib == Py_None)

  1047         return PyList_New(0);

  1048 

  1049     return PyDict_Keys(self->extra->attrib);

  1050 }

  1051 

  1052 static Py_ssize_t

  1053 element_length(ElementObject* self)

  1054 {

  1055     if (!self->extra)

  1056         return 0;

  1057 

  1058     return self->extra->length;

  1059 }

  1060 

  1061 static PyObject*

  1062 element_makeelement(PyObject* self, PyObject* args, PyObject* kw)

  1063 {

  1064     PyObject* elem;

  1065 

  1066     PyObject* tag;

  1067     PyObject* attrib;

  1068     if (!PyArg_ParseTuple(args, "OO:makeelement", &tag, &attrib))

  1069         return NULL;

  1070 

  1071     attrib = PyDict_Copy(attrib);

  1072     if (!attrib)

  1073         return NULL;

  1074 

  1075     elem = element_new(tag, attrib);

  1076 

  1077     Py_DECREF(attrib);

  1078 

  1079     return elem;

  1080 }

  1081 

  1082 static PyObject*

  1083 element_reduce(ElementObject* self, PyObject* args)

  1084 {

  1085     if (!PyArg_ParseTuple(args, ":__reduce__"))

  1086         return NULL;

  1087 

  1088     /* Hack alert: This method is used to work around a __copy__

  1089        problem on certain 2.3 and 2.4 versions.  To save time and

  1090        simplify the code, we create the copy in here, and use a dummy

  1091        copyelement helper to trick the copy module into doing the

  1092        right thing. */

  1093 

  1094     if (!elementtree_copyelement_obj) {

  1095         PyErr_SetString(

  1096             PyExc_RuntimeError,

  1097             "copyelement helper not found"

  1098             );

  1099         return NULL;

  1100     }

  1101 

  1102     return Py_BuildValue(

  1103         "O(N)", elementtree_copyelement_obj, element_copy(self, args)

  1104         );

  1105 }

  1106 

  1107 static PyObject*

  1108 element_remove(ElementObject* self, PyObject* args)

  1109 {

  1110     int i;

  1111 

  1112     PyObject* element;

  1113     if (!PyArg_ParseTuple(args, "O!:remove", &Element_Type, &element))

  1114         return NULL;

  1115 

  1116     if (!self->extra) {

  1117         /* element has no children, so raise exception */

  1118         PyErr_SetString(

  1119             PyExc_ValueError,

  1120             "list.remove(x): x not in list"

  1121             );

  1122         return NULL;

  1123     }

  1124 

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

  1126         if (self->extra->children[i] == element)

  1127             break;

  1128         if (PyObject_Compare(self->extra->children[i], element) == 0)

  1129             break;

  1130     }

  1131 

  1132     if (i == self->extra->length) {

  1133         /* element is not in children, so raise exception */

  1134         PyErr_SetString(

  1135             PyExc_ValueError,