/*

Original code by Lee Thomason (www.grinninglizard.com)

This software is provided 'as-is', without any express or implied

warranty. In no event will the authors be held liable for any

damages arising from the use of this software.

Permission is granted to anyone to use this software for any

purpose, including commercial applications, and to alter it and

redistribute it freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must

not claim that you wrote the original software. If you use this

software in a product, an acknowledgment in the product documentation

would be appreciated but is not required.

2. Altered source versions must be plainly marked as such, and

must not be misrepresented as being the original software.

3. This notice may not be removed or altered from any source

distribution.

*/

#include "tinyxml2.h"

#include <new> // yes, this one new style header, is in the Android SDK.

# ifdef ANDROID_NDK

# include <stddef.h>

#else

# include <cstddef>

#endif

static const char LINE_FEED = (char)0x0a; // all line endings are normalized to LF

static const char LF = LINE_FEED;

static const char CARRIAGE_RETURN = (char)0x0d; // CR gets filtered out

static const char CR = CARRIAGE_RETURN;

static const char SINGLE_QUOTE = '\'';

static const char DOUBLE_QUOTE = '\"';

// Bunch of unicode info at:

// http://www.unicode.org/faq/utf_bom.html

// ef bb bf (Microsoft "lead bytes") - designates UTF-8

static const unsigned char TIXML_UTF_LEAD_0 = 0xefU;

static const unsigned char TIXML_UTF_LEAD_1 = 0xbbU;

static const unsigned char TIXML_UTF_LEAD_2 = 0xbfU;

#define DELETE_NODE( node ) { \

if ( node ) { \

MemPool* pool = node->_memPool; \

node->~XMLNode(); \

pool->Free( node ); \

} \

}

#define DELETE_ATTRIBUTE( attrib ) { \

if ( attrib ) { \

MemPool* pool = attrib->_memPool; \

attrib->~XMLAttribute(); \

pool->Free( attrib ); \

} \

}

namespace tinyxml2

{

struct Entity {

const char* pattern;

int length;

char value;

};

static const int NUM_ENTITIES = 5;

static const Entity entities[NUM_ENTITIES] = {

{ "quot", 4, DOUBLE_QUOTE },

{ "amp", 3, '&' },

{ "apos", 4, SINGLE_QUOTE },

{ "lt", 2, '<' },

{ "gt", 2, '>' }

};

StrPair::~StrPair()

{

Reset();

}

void StrPair::Reset()

{

if ( _flags & NEEDS_DELETE ) {

delete [] _start;

}

_flags = 0;

_start = 0;

_end = 0;

}

void StrPair::SetStr( const char* str, int flags )

{

Reset();

size_t len = strlen( str );

_start = new char[ len+1 ];

memcpy( _start, str, len+1 );

_end = _start + len;

_flags = flags | NEEDS_DELETE;

}

char* StrPair::ParseText( char* p, const char* endTag, int strFlags )

{

TIXMLASSERT( endTag && *endTag );

char* start = p; // fixme: hides a member

char endChar = *endTag;

size_t length = strlen( endTag );

// Inner loop of text parsing.

while ( *p ) {

if ( *p == endChar && strncmp( p, endTag, length ) == 0 ) {

Set( start, p, strFlags );

return p + length;

}

++p;

}

return 0;

}

char* StrPair::ParseName( char* p )

{

char* start = p;

if ( !start || !(*start) ) {

return 0;

}

while( *p && ( p == start ? XMLUtil::IsNameStartChar( *p ) : XMLUtil::IsNameChar( *p ) )) {

++p;

}

if ( p > start ) {

Set( start, p, 0 );

return p;

}

return 0;

}

void StrPair::CollapseWhitespace()

{

// Trim leading space.

_start = XMLUtil::SkipWhiteSpace( _start );

if ( _start && *_start ) {

char* p = _start; // the read pointer

char* q = _start; // the write pointer

while( *p ) {

if ( XMLUtil::IsWhiteSpace( *p )) {

p = XMLUtil::SkipWhiteSpace( p );

if ( *p == 0 ) {

break; // don't write to q; this trims the trailing space.

}

*q = ' ';

++q;

}

*q = *p;

++q;

++p;

}

*q = 0;

}

}

const char* StrPair::GetStr()

{

if ( _flags & NEEDS_FLUSH ) {

*_end = 0;

_flags ^= NEEDS_FLUSH;

if ( _flags ) {

char* p = _start; // the read pointer

char* q = _start; // the write pointer

while( p < _end ) {

if ( (_flags & NEEDS_NEWLINE_NORMALIZATION) && *p == CR ) {

// CR-LF pair becomes LF

// CR alone becomes LF

// LF-CR becomes LF

if ( *(p+1) == LF ) {

p += 2;

}

else {

++p;

}

*q++ = LF;

}

else if ( (_flags & NEEDS_NEWLINE_NORMALIZATION) && *p == LF ) {

if ( *(p+1) == CR ) {

p += 2;

}

else {

++p;

}

*q++ = LF;

}

else if ( (_flags & NEEDS_ENTITY_PROCESSING) && *p == '&' ) {

// Entities handled by tinyXML2:

// - special entities in the entity table [in/out]

// - numeric character reference [in]

// &#20013; or &#x4e2d;

if ( *(p+1) == '#' ) {

char buf[10] = { 0 };

int len;

p = const_cast<char*>( XMLUtil::GetCharacterRef( p, buf, &len ) );

for( int i=0; i<len; ++i ) {

*q++ = buf[i];

}

TIXMLASSERT( q <= p );

}

else {

int i=0;

for(; i<NUM_ENTITIES; ++i ) {

if ( strncmp( p+1, entities[i].pattern, entities[i].length ) == 0

&& *(p+entities[i].length+1) == ';' ) {

// Found an entity convert;

*q = entities[i].value;

++q;

p += entities[i].length + 2;

break;

}

}

if ( i == NUM_ENTITIES ) {

// fixme: treat as error?

++p;

++q;

}

}

}

else {

*q = *p;

++p;

++q;

}

}

*q = 0;

}

// The loop below has plenty going on, and this

// is a less useful mode. Break it out.

if ( _flags & COLLAPSE_WHITESPACE ) {

CollapseWhitespace();

}

_flags = (_flags & NEEDS_DELETE);

}

return _start;

}

// --------- XMLUtil ----------- //

const char* XMLUtil::ReadBOM( const char* p, bool* bom )

{

*bom = false;

const unsigned char* pu = reinterpret_cast<const unsigned char*>(p);

// Check for BOM:

if ( *(pu+0) == TIXML_UTF_LEAD_0

&& *(pu+1) == TIXML_UTF_LEAD_1

&& *(pu+2) == TIXML_UTF_LEAD_2 ) {

*bom = true;

p += 3;

}

return p;

}

void XMLUtil::ConvertUTF32ToUTF8( unsigned long input, char* output, int* length )

{

const unsigned long BYTE_MASK = 0xBF;

const unsigned long BYTE_MARK = 0x80;

const unsigned long FIRST_BYTE_MARK[7] = { 0x00, 0x00, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC };

if (input < 0x80) {

*length = 1;

}

else if ( input < 0x800 ) {

*length = 2;

}

else if ( input < 0x10000 ) {

*length = 3;

}

else if ( input < 0x200000 ) {

*length = 4;

}

else {

*length = 0; // This code won't covert this correctly anyway.

return;

}

output += *length;

// Scary scary fall throughs.

switch (*length) {

case 4:

--output;

*output = (char)((input | BYTE_MARK) & BYTE_MASK);

input >>= 6;

case 3:

--output;

*output = (char)((input | BYTE_MARK) & BYTE_MASK);

input >>= 6;

case 2:

--output;

*output = (char)((input | BYTE_MARK) & BYTE_MASK);

input >>= 6;

case 1:

--output;

*output = (char)(input | FIRST_BYTE_MARK[*length]);

default:

break;

}

}

const char* XMLUtil::GetCharacterRef( const char* p, char* value, int* length )

{

// Presume an entity, and pull it out.

*length = 0;

if ( *(p+1) == '#' && *(p+2) ) {

unsigned long ucs = 0;

ptrdiff_t delta = 0;

unsigned mult = 1;

if ( *(p+2) == 'x' ) {

// Hexadecimal.

if ( !*(p+3) ) {

return 0;

}

const char* q = p+3;

q = strchr( q, ';' );

if ( !q || !*q ) {

return 0;

}

delta = q-p;

--q;

while ( *q != 'x' ) {

if ( *q >= '0' && *q <= '9' ) {

ucs += mult * (*q - '0');

}

else if ( *q >= 'a' && *q <= 'f' ) {

ucs += mult * (*q - 'a' + 10);

}

else if ( *q >= 'A' && *q <= 'F' ) {

ucs += mult * (*q - 'A' + 10 );

}

else {

return 0;

}

mult *= 16;

--q;

}

}

else {

// Decimal.

if ( !*(p+2) ) {

return 0;

}

const char* q = p+2;

q = strchr( q, ';' );

if ( !q || !*q ) {

return 0;

}

delta = q-p;

--q;

while ( *q != '#' ) {

if ( *q >= '0' && *q <= '9' ) {

ucs += mult * (*q - '0');

}

else {

return 0;

}

mult *= 10;

--q;

}

}

// convert the UCS to UTF-8

ConvertUTF32ToUTF8( ucs, value, length );

return p + delta + 1;

}

return p+1;

}

void XMLUtil::ToStr( int v, char* buffer, int bufferSize )

{

TIXML_SNPRINTF( buffer, bufferSize, "%d", v );

}

void XMLUtil::ToStr( unsigned v, char* buffer, int bufferSize )

{

TIXML_SNPRINTF( buffer, bufferSize, "%u", v );

}

void XMLUtil::ToStr( bool v, char* buffer, int bufferSize )

{

TIXML_SNPRINTF( buffer, bufferSize, "%d", v ? 1 : 0 );

}

void XMLUtil::ToStr( float v, char* buffer, int bufferSize )

{

TIXML_SNPRINTF( buffer, bufferSize, "%g", v );

}

void XMLUtil::ToStr( double v, char* buffer, int bufferSize )

{

TIXML_SNPRINTF( buffer, bufferSize, "%g", v );

}

bool XMLUtil::ToInt( const char* str, int* value )

{

if ( TIXML_SSCANF( str, "%d", value ) == 1 ) {

return true;

}

return false;

}

bool XMLUtil::ToUnsigned( const char* str, unsigned *value )

{

if ( TIXML_SSCANF( str, "%u", value ) == 1 ) {

return true;

}

return false;

}

bool XMLUtil::ToBool( const char* str, bool* value )

{

int ival = 0;

if ( ToInt( str, &ival )) {

*value = (ival==0) ? false : true;

return true;

}

if ( StringEqual( str, "true" ) ) {

*value = true;

return true;

}

else if ( StringEqual( str, "false" ) ) {

*value = false;

return true;

}

return false;

}

bool XMLUtil::ToFloat( const char* str, float* value )

{

if ( TIXML_SSCANF( str, "%f", value ) == 1 ) {

return true;

}

return false;

}

bool XMLUtil::ToDouble( const char* str, double* value )

{

if ( TIXML_SSCANF( str, "%lf", value ) == 1 ) {

return true;

}

return false;

}

char* XMLDocument::Identify( char* p, XMLNode** node )

{

XMLNode* returnNode = 0;

char* start = p;

p = XMLUtil::SkipWhiteSpace( p );

if( !p || !*p ) {

return p;

}

// What is this thing?

// - Elements start with a letter or underscore, but xml is reserved.

// - Comments: <!--

// - Decleration: <?

// - Everthing else is unknown to tinyxml.

//

static const char* xmlHeader = { "<?" };

static const char* commentHeader = { "<!--" };

static const char* dtdHeader = { "<!" };

static const char* cdataHeader = { "<![CDATA[" };

static const char* elementHeader = { "<" }; // and a header for everything else; check last.

static const int xmlHeaderLen = 2;

static const int commentHeaderLen = 4;

static const int dtdHeaderLen = 2;

static const int cdataHeaderLen = 9;

static const int elementHeaderLen = 1;

#if defined(_MSC_VER)

#pragma warning ( push )

#pragma warning ( disable : 4127 )

#endif

TIXMLASSERT( sizeof( XMLComment ) == sizeof( XMLUnknown ) ); // use same memory pool

TIXMLASSERT( sizeof( XMLComment ) == sizeof( XMLDeclaration ) ); // use same memory pool

#if defined(_MSC_VER)

#pragma warning (pop)

#endif

if ( XMLUtil::StringEqual( p, xmlHeader, xmlHeaderLen ) ) {

returnNode = new (_commentPool.Alloc()) XMLDeclaration( this );

returnNode->_memPool = &_commentPool;

p += xmlHeaderLen;

}

else if ( XMLUtil::StringEqual( p, commentHeader, commentHeaderLen ) ) {

returnNode = new (_commentPool.Alloc()) XMLComment( this );

returnNode->_memPool = &_commentPool;

p += commentHeaderLen;

}

else if ( XMLUtil::StringEqual( p, cdataHeader, cdataHeaderLen ) ) {

XMLText* text = new (_textPool.Alloc()) XMLText( this );

returnNode = text;

returnNode->_memPool = &_textPool;

p += cdataHeaderLen;

text->SetCData( true );

}

else if ( XMLUtil::StringEqual( p, dtdHeader, dtdHeaderLen ) ) {

returnNode = new (_commentPool.Alloc()) XMLUnknown( this );

returnNode->_memPool = &_commentPool;

p += dtdHeaderLen;

}

else if ( XMLUtil::StringEqual( p, elementHeader, elementHeaderLen ) ) {

returnNode = new (_elementPool.Alloc()) XMLElement( this );

returnNode->_memPool = &_elementPool;

p += elementHeaderLen;

}

else {

returnNode = new (_textPool.Alloc()) XMLText( this );

returnNode->_memPool = &_textPool;

p = start; // Back it up, all the text counts.

}

*node = returnNode;

return p;

}

bool XMLDocument::Accept( XMLVisitor* visitor ) const

{

if ( visitor->VisitEnter( *this ) ) {

for ( const XMLNode* node=FirstChild(); node; node=node->NextSibling() ) {

if ( !node->Accept( visitor ) ) {

break;

}

}

}

return visitor->VisitExit( *this );

}

// --------- XMLNode ----------- //

XMLNode::XMLNode( XMLDocument* doc ) :

_document( doc ),

_parent( 0 ),

_firstChild( 0 ), _lastChild( 0 ),

_prev( 0 ), _next( 0 )

{

}

XMLNode::~XMLNode()

{

DeleteChildren();

if ( _parent ) {

_parent->Unlink( this );

}

}

void XMLNode::SetValue( const char* str, bool staticMem )

{

if ( staticMem ) {

_value.SetInternedStr( str );

}

else {

_value.SetStr( str );

}

}

void XMLNode::DeleteChildren()

{

while( _firstChild ) {

XMLNode* node = _firstChild;

Unlink( node );

DELETE_NODE( node );

}

_firstChild = _lastChild = 0;

}

void XMLNode::Unlink( XMLNode* child )

{

TIXMLASSERT( child->_parent == this );

if ( child == _firstChild ) {

_firstChild = _firstChild->_next;

}

if ( child == _lastChild ) {

_lastChild = _lastChild->_prev;

}

if ( child->_prev ) {

child->_prev->_next = child->_next;

}

if ( child->_next ) {

child->_next->_prev = child->_prev;

}

child->_parent = 0;

}

void XMLNode::DeleteChild( XMLNode* node )

{

TIXMLASSERT( node->_parent == this );

DELETE_NODE( node );

}

XMLNode* XMLNode::InsertEndChild( XMLNode* addThis )

{

if ( _lastChild ) {

TIXMLASSERT( _firstChild );

TIXMLASSERT( _lastChild->_next == 0 );

_lastChild->_next = addThis;

addThis->_prev = _lastChild;

_lastChild = addThis;

addThis->_next = 0;

}

else {

TIXMLASSERT( _firstChild == 0 );

_firstChild = _lastChild = addThis;

addThis->_prev = 0;

addThis->_next = 0;

}

addThis->_parent = this;

addThis->_memPool->SetTracked();

return addThis;

}

XMLNode* XMLNode::InsertFirstChild( XMLNode* addThis )

{

if ( _firstChild ) {

TIXMLASSERT( _lastChild );

TIXMLASSERT( _firstChild->_prev == 0 );

_firstChild->_prev = addThis;

addThis->_next = _firstChild;

_firstChild = addThis;

addThis->_prev = 0;

}

else {

TIXMLASSERT( _lastChild == 0 );

_firstChild = _lastChild = addThis;

addThis->_prev = 0;

addThis->_next = 0;

}

addThis->_parent = this;

addThis->_memPool->SetTracked();

return addThis;

}

XMLNode* XMLNode::InsertAfterChild( XMLNode* afterThis, XMLNode* addThis )

{

TIXMLASSERT( afterThis->_parent == this );

if ( afterThis->_parent != this ) {

return 0;

}

if ( afterThis->_next == 0 ) {

// The last node or the only node.

return InsertEndChild( addThis );

}

addThis->_prev = afterThis;

addThis->_next = afterThis->_next;

afterThis->_next->_prev = addThis;

afterThis->_next = addThis;

addThis->_parent = this;

addThis->_memPool->SetTracked();

return addThis;

}

const XMLElement* XMLNode::FirstChildElement( const char* value ) const

{

for( XMLNode* node=_firstChild; node; node=node->_next ) {

XMLElement* element = node->ToElement();

if ( element ) {

if ( !value || XMLUtil::StringEqual( element->Name(), value ) ) {

return element;

}

}

}

return 0;

}

const XMLElement* XMLNode::LastChildElement( const char* value ) const

{

for( XMLNode* node=_lastChild; node; node=node->_prev ) {

XMLElement* element = node->ToElement();

if ( element ) {

if ( !value || XMLUtil::StringEqual( element->Name(), value ) ) {

return element;

}

}

}

return 0;

}

const XMLElement* XMLNode::NextSiblingElement( const char* value ) const

{

for( XMLNode* element=this->_next; element; element = element->_next ) {

if ( element->ToElement()

&& (!value || XMLUtil::StringEqual( value, element->Value() ))) {

return element->ToElement();

}

}

return 0;

}

const XMLElement* XMLNode::PreviousSiblingElement( const char* value ) const

{

for( XMLNode* element=_prev; element; element = element->_prev ) {

if ( element->ToElement()

&& (!value || XMLUtil::StringEqual( value, element->Value() ))) {

return element->ToElement();

}

}

return 0;

}

char* XMLNode::ParseDeep( char* p, StrPair* parentEnd )

{

// This is a recursive method, but thinking about it "at the current level"

// it is a pretty simple flat list:

// <foo/>

// <!-- comment -->

//

// With a special case:

// <foo>

// </foo>

// <!-- comment -->

//

// Where the closing element (/foo) *must* be the next thing after the opening

// element, and the names must match. BUT the tricky bit is that the closing

// element will be read by the child.

//

// 'endTag' is the end tag for this node, it is returned by a call to a child.

// 'parentEnd' is the end tag for the parent, which is filled in and returned.

while( p && *p ) {

XMLNode* node = 0;

p = _document->Identify( p, &node );

if ( p == 0 || node == 0 ) {

break;

}

StrPair endTag;

p = node->ParseDeep( p, &endTag );

if ( !p ) {

DELETE_NODE( node );

node = 0;

if ( !_document->Error() ) {

_document->SetError( XML_ERROR_PARSING, 0, 0 );

}

break;

}

// We read the end tag. Return it to the parent.

if ( node->ToElement() && node->ToElement()->ClosingType() == XMLElement::CLOSING ) {

if ( parentEnd ) {

*parentEnd = static_cast<XMLElement*>(node)->_value;

}

node->_memPool->SetTracked(); // created and then immediately deleted.

DELETE_NODE( node );

return p;

}

// Handle an end tag returned to this level.

// And handle a bunch of annoying errors.

XMLElement* ele = node->ToElement();

if ( ele ) {

if ( endTag.Empty() && ele->ClosingType() == XMLElement::OPEN ) {

_document->SetError( XML_ERROR_MISMATCHED_ELEMENT, node->Value(), 0 );

p = 0;

}

else if ( !endTag.Empty() && ele->ClosingType() != XMLElement::OPEN ) {

_document->SetError( XML_ERROR_MISMATCHED_ELEMENT, node->Value(), 0 );

p = 0;

}

else if ( !endTag.Empty() ) {

if ( !XMLUtil::StringEqual( endTag.GetStr(), node->Value() )) {

_document->SetError( XML_ERROR_MISMATCHED_ELEMENT, node->Value(), 0 );

p = 0;

}

}

}

if ( p == 0 ) {

DELETE_NODE( node );

node = 0;

}

if ( node ) {

this->InsertEndChild( node );

}

}

return 0;

}

// --------- XMLText ---------- //

char* XMLText::ParseDeep( char* p, StrPair* )

{

const char* start = p;

if ( this->CData() ) {

p = _value.ParseText( p, "]]>", StrPair::NEEDS_NEWLINE_NORMALIZATION );

if ( !p ) {

_document->SetError( XML_ERROR_PARSING_CDATA, start, 0 );

}

return p;

}

else {

int flags = _document->ProcessEntities() ? StrPair::TEXT_ELEMENT : StrPair::TEXT_ELEMENT_LEAVE_ENTITIES;

if ( _document->WhitespaceMode() == COLLAPSE_WHITESPACE ) {

flags |= StrPair::COLLAPSE_WHITESPACE;

}

p = _value.ParseText( p, "<", flags );

if ( !p ) {

_document->SetError( XML_ERROR_PARSING_TEXT, start, 0 );

}

if ( p && *p ) {

return p-1;

}

}

return 0;

}

XMLNode* XMLText::ShallowClone( XMLDocument* doc ) const

{

if ( !doc ) {

doc = _document;

}

XMLText* text = doc->NewText( Value() ); // fixme: this will always allocate memory. Intern?

text->SetCData( this->CData() );

return text;

}

bool XMLText::ShallowEqual( const XMLNode* compare ) const

{

return ( compare->ToText() && XMLUtil::StringEqual( compare->ToText()->Value(), Value() ));

}

bool XMLText::Accept( XMLVisitor* visitor ) const

{

return visitor->Visit( *this );

}

// --------- XMLComment ---------- //

XMLComment::XMLComment( XMLDocument* doc ) : XMLNode( doc )

{

}

XMLComment::~XMLComment()

{

}

char* XMLComment::ParseDeep( char* p, StrPair* )

{

// Comment parses as text.

const char* start = p;

p = _value.ParseText( p, "-->", StrPair::COMMENT );

if ( p == 0 ) {

_document->SetError( XML_ERROR_PARSING_COMMENT, start, 0 );

}

return p;

}

XMLNode* XMLComment::ShallowClone( XMLDocument* doc ) const

{

if ( !doc ) {

doc = _document;

}

XMLComment* comment = doc->NewComment( Value() ); // fixme: this will always allocate memory. Intern?

return comment;

}

bool XMLComment::ShallowEqual( const XMLNode* compare ) const

{

return ( compare->ToComment() && XMLUtil::StringEqual( compare->ToComment()->Value(), Value() ));

}

bool XMLComment::Accept( XMLVisitor* visitor ) const

{

return visitor->Visit( *this );

}

// --------- XMLDeclaration ---------- //

XMLDeclaration::XMLDeclaration( XMLDocument* doc ) : XMLNode( doc )

{

}

XMLDeclaration::~XMLDeclaration()

{

//printf( "~XMLDeclaration\n" );

}

char* XMLDeclaration::ParseDeep( char* p, StrPair* )

{

// Declaration parses as text.

const char* start = p;

p = _value.ParseText( p, "?>", StrPair::NEEDS_NEWLINE_NORMALIZATION );

if ( p == 0 ) {

_document->SetError( XML_ERROR_PARSING_DECLARATION, start, 0 );

}

return p;

}

XMLNode* XMLDeclaration::ShallowClone( XMLDocument* doc ) const

{

if ( !doc ) {

doc = _document;

}

XMLDeclaration* dec = doc->NewDeclaration( Value() ); // fixme: this will always allocate memory. Intern?

return dec;

}

bool XMLDeclaration::ShallowEqual( const XMLNode* compare ) const

{

return ( compare->ToDeclaration() && XMLUtil::StringEqual( compare->ToDeclaration()->Value(), Value() ));

}

bool XMLDeclaration::Accept( XMLVisitor* visitor ) const

{

return visitor->Visit( *this );

}

// --------- XMLUnknown ---------- //

XMLUnknown::XMLUnknown( XMLDocument* doc ) : XMLNode( doc )

{

}