/*

 * tree.c : implementation of access function for an XML tree.

 *

 * References:

 *   XHTML 1.0 W3C REC: http://www.w3.org/TR/2002/REC-xhtml1-20020801/

 *

 * See Copyright for the status of this software.

 *

 * daniel@veillard.com

 *

 */

#pragma warning(disable: 4127 4132)

#define IN_LIBXML

#include "XmlEnglibxml.h"

#include <string.h> /* for memset() only ! */

// TODO: XE Cleanup

#ifdef HAVE_CTYPE_H

#include <ctype.h>

#endif

#ifdef HAVE_STDLIB_H

#include <stdlib.h>

#endif

#ifdef HAVE_ZLIB_H

#include <zlib.h>

#endif

#include "Libxml2_globals.h"

#include "Libxml2_uri.h"

#include "Libxml2_parserInternals.h"

#ifdef LIBXML_HTML_ENABLED

#include "Libxml2_HTMLtree.h"

#endif

xmlNsPtr xmlNewReconciliedNs(xmlDocPtr doc, xmlNodePtr tree, xmlNsPtr ns);

/************************************************************************

 *                                                                      *

 *      Tree memory error handler                                       *

 *                                                                      *

 ************************************************************************/

/**

 * xmlTreeErrMemory:

 * @extra:  extra informations

 *

 * Handle an out of memory condition

 */

static void

xmlTreeErrMemory(const char *extra)

{

    SET_OOM_FLAG;

    __xmlSimpleError(XML_FROM_TREE, XML_ERR_NO_MEMORY, NULL, NULL, extra);

}

// TODO: CLEANUP

/**

 * xmlTreeErr:

 * @code:  the error number

 * @extra:  extra informations

 *

 * Handle an out of memory condition

 */

static void

xmlTreeErr(int code, xmlNodePtr node, const char *extra)

{

    const char *msg = NULL;

    switch(code) {

        case XML_TREE_INVALID_HEX:

        msg = EMBED_ERRTXT("invalid hexadecimal character value");

        break;

    case XML_TREE_INVALID_DEC:

        msg = "invalid decimal character value";

        break;

    case XML_TREE_UNTERMINATED_ENTITY:

        msg = EMBED_ERRTXT("unterminated entity reference %15s");

        break;

    default:

        msg = EMBED_ERRTXT("unexpected error number");

    }

    __xmlSimpleError(XML_FROM_TREE, code, node, msg, extra);

}

/************************************************************************

 *                                                                      *

 *      A few static variables and macros                               *

 *                                                                      *

 ************************************************************************/

// TODO: Consider making this a function / make if a function-like macros (it does not use ; inthe end now)

#define UPDATE_LAST_CHILD_AND_PARENT(n)                             \

    if ((n) != NULL) {                                              \

        xmlNodePtr ulccur = (n)->children;                          \

        if (ulccur == NULL) {                                       \

            (n)->last = NULL;                                       \

        } else {                                                    \

            while (ulccur->next != NULL) {                          \

                ulccur->parent = (n);                               \

            ulccur = ulccur->next;                                  \

        }                                                           \

        ulccur->parent = (n);                                       \

        (n)->last = ulccur;                                         \

    }}

/* #define DEBUG_BUFFER */

/* #define DEBUG_TREE */

/************************************************************************

 *                                                                      *

 *      Functions to move to entities.c once the                        *

 *      API freeze is smoothen and they can be made public.             *

 *                                                                      *

 ************************************************************************/

//#include "Libxml2_hash.h" // included via parser.h

#ifdef LIBXML_TREE_ENABLED

/**

 * xmlGetEntityFromDtd:

 * @dtd:  A pointer to the DTD to search

 * @name:  The entity name

 *

 * Do an entity lookup in the DTD entity hash table and

 * return the corresponding entity, if found.

 *

 * Returns A pointer to the entity structure or NULL if not found.

 */

static xmlEntityPtr

xmlGetEntityFromDtd(xmlDtdPtr dtd, const xmlChar *name) {

    xmlEntitiesTablePtr table;

    if((dtd != NULL) && (dtd->entities != NULL)) {

        table = (xmlEntitiesTablePtr) dtd->entities;

        return((xmlEntityPtr) xmlHashLookup(table, name));

        /* return(xmlGetEntityFromTable(table, name)); */

    }

    return(NULL);

}

/**

 * xmlGetParameterEntityFromDtd:

 * @dtd:  A pointer to the DTD to search

 * @name:  The entity name

 *

 * Do an entity lookup in the DTD pararmeter entity hash table and

 * return the corresponding entity, if found.

 *

 * Returns A pointer to the entity structure or NULL if not found.

 */

static xmlEntityPtr

xmlGetParameterEntityFromDtd(xmlDtdPtr dtd, const xmlChar *name) {

    xmlEntitiesTablePtr table;

    if ((dtd != NULL) && (dtd->pentities != NULL)) {

    table = (xmlEntitiesTablePtr) dtd->pentities;

    return((xmlEntityPtr) xmlHashLookup(table, name));

    /* return(xmlGetEntityFromTable(table, name)); */

    }

    return(NULL);

}

#endif /* LIBXML_TREE_ENABLED */

/************************************************************************

 *                                                                      *

 *          QName handling helper                                       *

 *                                                                      *

 ************************************************************************/

/**

 * xmlBuildQName:

 * @ncname:  the Name

 * @prefix:  the prefix

 * @memory:  preallocated memory

 * @len:  preallocated memory length

 *

 * Builds the QName @prefix:@ncname in @memory if there is enough space

 * and prefix is not NULL nor empty, otherwise allocate a new string.

 * If prefix is NULL or empty it returns ncname.

 *

 * Returns the new string which must be freed by the caller if different from

 *         @memory and @ncname or NULL in case of error

 *

 * OOM: possible --> returns NULL, OOM flag is set

 */

xmlChar *

xmlBuildQName(const xmlChar *ncname, const xmlChar *prefix,

              xmlChar *memory, int len)

{

    int lenn, lenp;

    xmlChar *ret;

    if (ncname == NULL) return(NULL);

    if (prefix == NULL) return((xmlChar *) ncname);

    lenn = strlen((char *) ncname);

    lenp = strlen((char *) prefix);

    if ((memory == NULL) || (len < lenn + lenp + 2)) {

        ret = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);

        if (ret == NULL) {

            xmlTreeErrMemory(EMBED_ERRTXT("building QName"));

            return(NULL);

        }

    } else {

        ret = memory;

    }

    memcpy(&ret[0], prefix, lenp);

    ret[lenp] = ':';

    memcpy(&ret[lenp + 1], ncname, lenn);

    ret[lenn + lenp + 1] = 0;

    return(ret);

}

/**

 * xmlSplitQName2:

 * @name:  the full QName

 * @prefix:  a xmlChar **

 *

 * parse an XML qualified name string

 *

 * [NS 5] QName ::= (Prefix ':')? LocalPart

 *

 * [NS 6] Prefix ::= NCName

 *

 * [NS 7] LocalPart ::= NCName

 *

 * Returns NULL if not a QName, otherwise the local part, and prefix

 *   is updated to get the Prefix if any.

 *

 * OOM: possible --> iif returns NULL and OOM flag is set

 */

xmlChar*

xmlSplitQName2(const xmlChar *name, xmlChar **prefix) {

    int len = 0;

    xmlChar *ret = NULL;

    *prefix = NULL;

    if (name == NULL) return(NULL);

#ifndef XML_XML_NAMESPACE

    /* xml: prefix is not really a namespace */

    if ((name[0] == 'x') && (name[1] == 'm') &&

        (name[2] == 'l') && (name[3] == ':'))

        return(NULL);

#endif

    /* nasty but valid */

    if (name[0] == ':')

        return(NULL);

    /*

     * we are not trying to validate but just to cut, and yes it will

     * work even if this is as set of UTF-8 encoded chars

     */

    while ((name[len] != 0) && (name[len] != ':'))

        len++;

    if (name[len] == 0)

        return(NULL);

    *prefix = xmlStrndup(name, len);

    if (*prefix == NULL) {

        xmlTreeErrMemory(EMBED_ERRTXT("QName split"));

        return(NULL);

    }

    ret = xmlStrdup(&name[len + 1]);

    if (ret == NULL) {

        xmlTreeErrMemory(EMBED_ERRTXT("QName split"));

        if (*prefix != NULL) {

            xmlFree(*prefix);

            *prefix = NULL;

        }

        return(NULL);

    }

    return(ret);

}

/**

 * xmlSplitQName3:

 * @name:  the full QName

 * @len: an int *

 *

 * parse an XML qualified name string,i

 *

 * returns NULL if it is not a Qualified Name, otherwise, update len

 *         with the lenght in byte of the prefix and return a pointer

 */

const xmlChar *

xmlSplitQName3(const xmlChar *name, int *len) {

    int i = 0;

    if (name == NULL) return(NULL);

    if (len == NULL) return(NULL);

    /* nasty but valid */

    if (name[0] == ':')

        return(NULL);

    /*

     * we are not trying to validate but just to cut, and yes it will

     * work even if this is as set of UTF-8 encoded chars

     */

    while ((name[i] != 0) && (name[i] != ':'))

        i++;

    if (name[i] == 0)

        return(NULL);

    *len = i;

    return(&name[i+1]);

}

/************************************************************************

 *                                                                      *

 *      Check Name, NCName and QName strings                            *

 *                                                                      *

 ************************************************************************/

#define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)

#if defined(LIBXML_TREE_ENABLED) || defined(LIBXML_XPATH_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED)

/**

 * xmlValidateNCName:

 * @value: the value to check

 * @space: allow spaces in front and end of the string

 *

 * Check that a value conforms to the lexical space of NCName

 *

 * Returns 0 if this validates, a positive error code number otherwise

 *         and -1 in case of internal or API error.

 */

int

xmlValidateNCName(const xmlChar *value, int space) {

    const xmlChar *cur = value;

    int c,l;

    /*

     * First quick algorithm for ASCII range

     */

    if (space)

    while (IS_BLANK_CH(*cur)) cur++;

    if (((*cur >= 'a') && (*cur <= 'z')) ||

        ((*cur >= 'A') && (*cur <= 'Z')) ||

        (*cur == '_'))

        cur++;

    else

        goto try_complex;

    while (((*cur >= 'a') && (*cur <= 'z')) ||

        ((*cur >= 'A') && (*cur <= 'Z')) ||

        ((*cur >= '0') && (*cur <= '9')) ||

         (*cur == '_') || (*cur == '-') || (*cur == '.'))

    {

        cur++;

    }

    if (space)

        while (IS_BLANK_CH(*cur)) cur++;

    if (*cur == 0)

        return(0);

try_complex:

    /*

     * Second check for chars outside the ASCII range

     */

    cur = value;

    c = CUR_SCHAR(cur, l);

    if (space) {

        while (IS_BLANK(c)) {

            cur += l;

            c = CUR_SCHAR(cur, l);

        }

    }

    if ((!IS_LETTER(c)) && (c != '_'))

        return(1);

    cur += l;

    c = CUR_SCHAR(cur, l);

    while (IS_LETTER(c) || IS_DIGIT(c) ||

          (c == '.') || (c == '-') || (c == '_') ||

           IS_COMBINING(c) || IS_EXTENDER(c))

    {

        cur += l;

        c = CUR_SCHAR(cur, l);

    }

    if (space) {

        while (IS_BLANK(c)) {

            cur += l;

            c = CUR_SCHAR(cur, l);

        }

    }

    if (c != 0)

        return(1);

    return(0);

}

#endif

#if defined(LIBXML_TREE_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED)

/**

 * xmlValidateQName:

 * @value: the value to check

 * @space: allow spaces in front and end of the string

 *

 * Check that a value conforms to the lexical space of QName

 *

 * Returns 0 if this validates, a positive error code number otherwise

 *         and -1 in case of internal or API error.

 */

int

xmlValidateQName(const xmlChar *value, int space) {

    const xmlChar *cur = value;

    int c,l;

    /*

     * First quick algorithm for ASCII range

     */

    if (space)

    while (IS_BLANK_CH(*cur)) cur++;

    if (((*cur >= 'a') && (*cur <= 'z')) || ((*cur >= 'A') && (*cur <= 'Z')) ||

    (*cur == '_'))

    cur++;

    else

    goto try_complex;

    while (((*cur >= 'a') && (*cur <= 'z')) ||

       ((*cur >= 'A') && (*cur <= 'Z')) ||

       ((*cur >= '0') && (*cur <= '9')) ||

       (*cur == '_') || (*cur == '-') || (*cur == '.'))

    cur++;

    if (*cur == ':') {

    cur++;

    if (((*cur >= 'a') && (*cur <= 'z')) ||

        ((*cur >= 'A') && (*cur <= 'Z')) ||

        (*cur == '_'))

        cur++;

    else

        goto try_complex;

    while (((*cur >= 'a') && (*cur <= 'z')) ||

           ((*cur >= 'A') && (*cur <= 'Z')) ||

           ((*cur >= '0') && (*cur <= '9')) ||

           (*cur == '_') || (*cur == '-') || (*cur == '.'))

        cur++;

    }

    if (space)

    while (IS_BLANK_CH(*cur)) cur++;

    if (*cur == 0)

    return(0);

try_complex:

    /*

     * Second check for chars outside the ASCII range

     */

    cur = value;

    c = CUR_SCHAR(cur, l);

    if (space) {

    while (IS_BLANK(c)) {

        cur += l;

        c = CUR_SCHAR(cur, l);

    }

    }

    if ((!IS_LETTER(c)) && (c != '_'))

    return(1);

    cur += l;

    c = CUR_SCHAR(cur, l);

    while (IS_LETTER(c) || IS_DIGIT(c) || (c == '.') ||

       (c == '-') || (c == '_') || IS_COMBINING(c) ||

       IS_EXTENDER(c)) {

    cur += l;

    c = CUR_SCHAR(cur, l);

    }

    if (c == ':') {

    cur += l;

    c = CUR_SCHAR(cur, l);

    if ((!IS_LETTER(c)) && (c != '_'))

        return(1);

    cur += l;

    c = CUR_SCHAR(cur, l);

    while (IS_LETTER(c) || IS_DIGIT(c) || (c == '.') ||

           (c == '-') || (c == '_') || IS_COMBINING(c) ||

           IS_EXTENDER(c)) {

        cur += l;

        c = CUR_SCHAR(cur, l);

    }

    }

    if (space) {

    while (IS_BLANK(c)) {

        cur += l;

        c = CUR_SCHAR(cur, l);

    }

    }

    if (c != 0)

    return(1);

    return(0);

}

/**

 * xmlValidateName:

 * @value: the value to check

 * @space: allow spaces in front and end of the string

 *

 * Check that a value conforms to the lexical space of Name

 *

 * Returns 0 if this validates, a positive error code number otherwise

 *         and -1 in case of internal or API error.

 */

int

xmlValidateName(const xmlChar *value, int space) {

    const xmlChar *cur = value;

    int c,l;

    /*

     * First quick algorithm for ASCII range

     */

    if (space)

    while (IS_BLANK_CH(*cur)) cur++;

    if (((*cur >= 'a') && (*cur <= 'z')) || ((*cur >= 'A') && (*cur <= 'Z')) ||

    (*cur == '_') || (*cur == ':'))

    cur++;

    else

    goto try_complex;

    while (((*cur >= 'a') && (*cur <= 'z')) ||

       ((*cur >= 'A') && (*cur <= 'Z')) ||