1 /*
2   Copyright (c) 2005-2019 by Jakob Schröter <js@camaya.net>
3   This file is part of the gloox library. http://camaya.net/gloox
4 
5   This software is distributed under a license. The full license
6   agreement can be found in the file LICENSE in this distribution.
7   This software may not be copied, modified, sold or distributed
8   other than expressed in the named license agreement.
9 
10   This software is distributed without any warranty.
11 */
12 
13 
14 #include "tag.h"
15 #include "util.h"
16 
17 #include <ctype.h>
18 #include <stdlib.h>
19 
20 #include <algorithm>
21 
22 namespace gloox
23 {
24 
25   // ---- Tag::Attribute ----
Attribute(Tag * parent,const std::string & name,const std::string & value,const std::string & xmlns)26   Tag::Attribute::Attribute( Tag* parent, const std::string& name, const std::string& value,
27                              const std::string& xmlns )
28     : m_parent( parent )
29   {
30     if( m_parent )
31       m_parent->addAttribute( this );
32 
33     init( name, value, xmlns );
34   }
35 
Attribute(const std::string & name,const std::string & value,const std::string & xmlns)36   Tag::Attribute::Attribute( const std::string& name, const std::string& value,
37                              const std::string& xmlns )
38     : m_parent( 0 )
39   {
40     init( name, value, xmlns );
41   }
42 
Attribute(const Attribute & attr)43   Tag::Attribute::Attribute( const Attribute& attr )
44     : m_parent( attr.m_parent ), m_name( attr.m_name ), m_value( attr.m_value ),
45       m_xmlns( attr.m_xmlns ), m_prefix( attr.m_prefix )
46   {
47   }
48 
init(const std::string & name,const std::string & value,const std::string & xmlns)49   void Tag::Attribute::init( const std::string& name, const std::string& value,
50                              const std::string& xmlns )
51   {
52     if( util::checkValidXMLChars( xmlns ) )
53       m_xmlns = xmlns;
54     else
55       return;
56 
57     if( util::checkValidXMLChars( value ) )
58       m_value = value;
59     else
60       return;
61 
62     if( util::checkValidXMLChars( name ) )
63       m_name = name;
64     else
65       return;
66   }
67 
setValue(const std::string & value)68   bool Tag::Attribute::setValue( const std::string& value )
69   {
70     if( !util::checkValidXMLChars( value ) )
71       return false;
72 
73     m_value = value;
74     return true;
75   }
76 
setXmlns(const std::string & xmlns)77   bool Tag::Attribute::setXmlns( const std::string& xmlns )
78   {
79     if( !util::checkValidXMLChars( xmlns ) )
80       return false;
81 
82     m_xmlns = xmlns;
83     return true;
84   }
85 
setPrefix(const std::string & prefix)86   bool Tag::Attribute::setPrefix( const std::string& prefix )
87   {
88     if( !util::checkValidXMLChars( prefix ) )
89       return false;
90 
91     m_prefix = prefix;
92     return true;
93   }
94 
xmlns() const95   const std::string Tag::Attribute::xmlns() const
96   {
97     if( !m_xmlns.empty() )
98       return m_xmlns;
99 
100     if( m_parent && !m_prefix.empty() )
101       return m_parent->xmlns( m_prefix );
102 
103     return EmptyString;
104   }
105 
prefix() const106   const std::string& Tag::Attribute::prefix() const
107   {
108     if( !m_prefix.empty() )
109       return m_prefix;
110 
111     if( m_parent )
112       return m_parent->prefix( m_xmlns );
113 
114     return EmptyString;
115   }
116 
xml() const117   const std::string Tag::Attribute::xml() const
118   {
119     if( m_name.empty() )
120       return EmptyString;
121 
122     std::string xml;
123     xml += ' ';
124     if( !m_prefix.empty() )
125     {
126       xml += m_prefix;
127       xml += ':';
128     }
129     xml += m_name;
130     xml += "='";
131     util::appendEscaped( xml, m_value );
132     xml += '\'';
133 
134     return xml;
135   }
136   // ---- ~Tag::Attribute ----
137 
138   // ---- Tag ----
Tag(const std::string & name,const std::string & cdata)139   Tag::Tag( const std::string& name, const std::string& cdata )
140     : m_parent( 0 ), m_children( 0 ), m_cdata( 0 ),
141       m_attribs( 0 ), m_nodes( 0 ),
142       m_xmlnss( 0 )
143   {
144     addCData( cdata ); // implicitly UTF-8 checked
145 
146     if( util::checkValidXMLChars( name ) )
147       m_name = name;
148   }
149 
Tag(Tag * parent,const std::string & name,const std::string & cdata)150   Tag::Tag( Tag* parent, const std::string& name, const std::string& cdata )
151     : m_parent( parent ), m_children( 0 ), m_cdata( 0 ),
152       m_attribs( 0 ), m_nodes( 0 ),
153       m_xmlnss( 0 )
154   {
155     if( m_parent )
156       m_parent->addChild( this );
157 
158     addCData( cdata ); // implicitly UTF-8 checked
159 
160     if( util::checkValidXMLChars( name ) )
161       m_name = name;
162   }
163 
Tag(const std::string & name,const std::string & attrib,const std::string & value)164   Tag::Tag( const std::string& name,
165             const std::string& attrib,
166             const std::string& value )
167     : m_parent( 0 ), m_children( 0 ), m_cdata( 0 ),
168       m_attribs( 0 ), m_nodes( 0 ),
169       m_name( name ), m_xmlnss( 0 )
170   {
171     addAttribute( attrib, value ); // implicitly UTF-8 checked
172 
173     if( util::checkValidXMLChars( name ) )
174       m_name = name;
175   }
176 
Tag(Tag * parent,const std::string & name,const std::string & attrib,const std::string & value)177   Tag::Tag( Tag* parent, const std::string& name,
178                          const std::string& attrib,
179                          const std::string& value )
180     : m_parent( parent ), m_children( 0 ), m_cdata( 0 ),
181       m_attribs( 0 ), m_nodes( 0 ),
182       m_name( name ), m_xmlnss( 0 )
183   {
184     if( m_parent )
185       m_parent->addChild( this );
186 
187     addAttribute( attrib, value ); // implicitly UTF-8 checked
188 
189     if( util::checkValidXMLChars( name ) )
190       m_name = name;
191   }
192 
Tag(Tag * tag)193   Tag::Tag( Tag* tag )
194     : m_parent( 0 ), m_children( 0 ), m_cdata( 0 ), m_attribs( 0 ),
195       m_nodes( 0 ), m_xmlnss( 0 )
196   {
197     if( !tag )
198       return;
199 
200     m_children = tag->m_children;
201     m_cdata = tag->m_cdata;
202     m_attribs = tag->m_attribs;
203     m_nodes = tag->m_nodes;
204     m_name = tag->m_name;
205     m_xmlns = tag->m_xmlns;
206     m_xmlnss = tag->m_xmlnss;
207 
208     tag->m_nodes = 0;
209     tag->m_cdata = 0;
210     tag->m_attribs = 0;
211     tag->m_children = 0;
212     tag->m_xmlnss = 0;
213 
214     if( m_attribs )
215     {
216       AttributeList::iterator it = m_attribs->begin();
217       while( it != m_attribs->end() )
218         (*it++)->m_parent = this;
219     }
220 
221     if( m_children )
222     {
223       TagList::iterator it = m_children->begin();
224       while( it != m_children->end() )
225         (*it++)->m_parent = this;
226     }
227   }
228 
~Tag()229   Tag::~Tag()
230   {
231     if( m_cdata )
232       util::clearList( *m_cdata );
233     if( m_attribs )
234       util::clearList( *m_attribs );
235     if( m_children )
236       util::clearList( *m_children );
237     if( m_nodes )
238       util::clearList( *m_nodes );
239 
240     delete m_cdata;
241     delete m_attribs;
242     delete m_children;
243     delete m_nodes;
244     delete m_xmlnss;
245 
246     m_parent = 0;
247   }
248 
operator ==(const Tag & right) const249   bool Tag::operator==( const Tag& right ) const
250   {
251     if( m_name != right.m_name || m_xmlns != right.m_xmlns )
252       return false;
253 
254     if( m_cdata && right.m_cdata )
255     {
256       StringPList::const_iterator ct = m_cdata->begin();
257       StringPList::const_iterator ct_r = right.m_cdata->begin();
258       while( ct != m_cdata->end() && ct_r != right.m_cdata->end() && *(*ct) == *(*ct_r) )
259       {
260         ++ct;
261         ++ct_r;
262       }
263       if( ct != m_cdata->end() )
264         return false;
265     }
266     else if( m_cdata || right.m_cdata )
267       return false;
268 
269     if( m_children && right.m_children )
270     {
271       TagList::const_iterator it = m_children->begin();
272       TagList::const_iterator it_r = right.m_children->begin();
273       while( it != m_children->end() && it_r != right.m_children->end() && *(*it) == *(*it_r) )
274       {
275         ++it;
276         ++it_r;
277       }
278       if( it != m_children->end() )
279         return false;
280     }
281     else if( m_children || right.m_children )
282       return false;
283 
284     if( m_attribs && right.m_attribs )
285     {
286       AttributeList::const_iterator at = m_attribs->begin();
287       AttributeList::const_iterator at_r = right.m_attribs->begin();
288       while( at != m_attribs->end() && at_r != right.m_attribs->end() && *(*at) == *(*at_r) )
289       {
290         ++at;
291         ++at_r;
292       }
293       if( at != m_attribs->end() )
294         return false;
295     }
296     else if( m_attribs || right.m_attribs )
297       return false;
298 
299     return true;
300   }
301 
xml() const302   const std::string Tag::xml() const
303   {
304     if( m_name.empty() )
305       return EmptyString;
306 
307     std::string xml = "<";
308     if( !m_prefix.empty() )
309     {
310       xml += m_prefix;
311       xml += ':';
312     }
313     xml += m_name;
314     if( m_attribs && !m_attribs->empty() )
315     {
316       AttributeList::const_iterator it_a = m_attribs->begin();
317       for( ; it_a != m_attribs->end(); ++it_a )
318       {
319         xml += (*it_a)->xml();
320       }
321     }
322 
323     if( !m_nodes || m_nodes->empty() )
324       xml += "/>";
325     else
326     {
327       xml += '>';
328       NodeList::const_iterator it_n = m_nodes->begin();
329       for( ; it_n != m_nodes->end(); ++it_n )
330       {
331         switch( (*it_n)->type )
332         {
333           case TypeTag:
334             xml += (*it_n)->tag->xml();
335             break;
336           case TypeString:
337             util::appendEscaped( xml, *((*it_n)->str) );
338             break;
339         }
340       }
341       xml += "</";
342       if( !m_prefix.empty() )
343       {
344         xml += m_prefix;
345         xml += ':';
346       }
347       xml += m_name;
348       xml += '>';
349     }
350 
351     return xml;
352   }
353 
addAttribute(Attribute * attr)354   bool Tag::addAttribute( Attribute* attr )
355   {
356     if( !attr )
357       return false;
358 
359     if( !(*attr) )
360     {
361       delete attr;
362       return false;
363     }
364 
365     if( !m_attribs )
366       m_attribs = new AttributeList();
367 
368     AttributeList::iterator it = m_attribs->begin();
369     for( ; it != m_attribs->end(); ++it )
370     {
371       if( (*it)->name() == attr->name()
372           && ( (*it)->xmlns() == attr->xmlns() || (*it)->prefix() == attr->prefix() ) )
373       {
374         delete (*it);
375         (*it) = attr;
376         return true;
377       }
378     }
379 
380     m_attribs->push_back( attr );
381 
382     return true;
383   }
384 
addAttribute(const std::string & name,const std::string & value)385   bool Tag::addAttribute( const std::string& name, const std::string& value )
386   {
387     if( name.empty() || value.empty() )
388       return false;
389 
390     return addAttribute( new Attribute( name, value ) );
391   }
392 
addAttribute(const std::string & name,int value)393   bool Tag::addAttribute( const std::string& name, int value )
394   {
395     if( name.empty() )
396       return false;
397 
398     return addAttribute( name, util::int2string( value ) );
399   }
400 
addAttribute(const std::string & name,long value)401   bool Tag::addAttribute( const std::string& name, long value )
402   {
403     if( name.empty() )
404       return false;
405 
406     return addAttribute( name, util::long2string( value ) );
407   }
408 
setAttributes(const AttributeList & attributes)409   void Tag::setAttributes( const AttributeList& attributes )
410   {
411     if( !m_attribs )
412       m_attribs = new AttributeList( attributes );
413     else
414     {
415       util::clearList( *m_attribs );
416       *m_attribs = attributes;
417     }
418 
419     AttributeList::iterator it = m_attribs->begin();
420     for( ; it != m_attribs->end(); ++it )
421       (*it)->m_parent = this;
422   }
423 
addChild(Tag * child)424   void Tag::addChild( Tag* child )
425   {
426     if( !child )
427       return;
428 
429     if( !m_nodes )
430       m_nodes = new NodeList();
431     if( !m_children )
432       m_children = new TagList();
433 
434     m_children->push_back( child );
435     child->m_parent = this;
436     m_nodes->push_back( new Node( TypeTag, child ) );
437   }
438 
addChildCopy(const Tag * child)439   void Tag::addChildCopy( const Tag* child )
440   {
441     if( !child )
442       return;
443 
444     addChild( child->clone() );
445   }
446 
setCData(const std::string & cdata)447   bool Tag::setCData( const std::string& cdata )
448   {
449     if( cdata.empty() || !util::checkValidXMLChars( cdata ) )
450       return false;
451 
452     if( !m_cdata )
453       m_cdata = new StringPList();
454     else
455       util::clearList( *m_cdata );
456 
457     if( !m_nodes )
458       m_nodes = new NodeList();
459     else
460     {
461       NodeList::iterator it = m_nodes->begin();
462       NodeList::iterator t;
463       while( it != m_nodes->end() )
464       {
465         if( (*it)->type == TypeString )
466         {
467           t = it++;
468           delete (*t);
469           m_nodes->erase( t );
470         }
471         else
472         {
473            it++;
474         }
475       }
476     }
477 
478     return addCData( cdata );
479   }
480 
addCData(const std::string & cdata)481   bool Tag::addCData( const std::string& cdata )
482   {
483     if( cdata.empty() || !util::checkValidXMLChars( cdata ) )
484       return false;
485 
486     if( !m_cdata )
487       m_cdata = new StringPList();
488     if( !m_nodes )
489       m_nodes = new NodeList();
490 
491     std::string* str = new std::string( cdata );
492     m_cdata->push_back( str );
493     m_nodes->push_back( new Node( TypeString, str ) );
494     return true;
495   }
496 
cdata() const497   const std::string Tag::cdata() const
498   {
499     if( !m_cdata )
500       return EmptyString;
501 
502     std::string str;
503     StringPList::const_iterator it = m_cdata->begin();
504     for( ; it != m_cdata->end(); ++it )
505       str += *(*it);
506 
507     return str;
508   }
509 
children() const510   const TagList& Tag::children() const
511   {
512     static const TagList empty;
513     return m_children ? *m_children : empty;
514   }
515 
attributes() const516   const Tag::AttributeList& Tag::attributes() const
517   {
518     static const AttributeList empty;
519     return m_attribs ? *m_attribs : empty;
520   }
521 
setXmlns(const std::string & xmlns,const std::string & prefix)522   bool Tag::setXmlns( const std::string& xmlns, const std::string& prefix )
523   {
524     if( !util::checkValidXMLChars( xmlns ) || !util::checkValidXMLChars( prefix ) )
525       return false;
526 
527     if( prefix.empty() )
528     {
529       m_xmlns = xmlns;
530       return addAttribute( XMLNS, m_xmlns );
531     }
532     else
533     {
534       if( !m_xmlnss )
535         m_xmlnss = new StringMap();
536 
537       (*m_xmlnss)[prefix] = xmlns;
538 
539       return addAttribute( XMLNS + ":" + prefix, xmlns );
540     }
541   }
542 
xmlns() const543   const std::string Tag::xmlns() const
544   {
545     return xmlns( m_prefix );
546   }
547 
xmlns(const std::string & prefix) const548   const std::string Tag::xmlns( const std::string& prefix ) const
549   {
550     if( prefix.empty() )
551     {
552       return hasAttribute( XMLNS ) ? findAttribute( XMLNS ) : m_xmlns;
553     }
554 
555     if( m_xmlnss )
556     {
557       StringMap::const_iterator it = m_xmlnss->find( prefix );
558       if( it != m_xmlnss->end() )
559         return (*it).second;
560     }
561 
562     return m_parent ? m_parent->xmlns( prefix ) : EmptyString;
563   }
564 
setPrefix(const std::string & prefix)565   bool Tag::setPrefix( const std::string& prefix )
566   {
567     if( !util::checkValidXMLChars( prefix ) )
568       return false;
569 
570     m_prefix = prefix;
571     return true;
572   }
573 
prefix(const std::string & xmlns) const574   const std::string& Tag::prefix( const std::string& xmlns ) const
575   {
576     if( xmlns.empty() || !m_xmlnss )
577       return EmptyString;
578 
579     StringMap::const_iterator it = m_xmlnss->begin();
580     for( ; it != m_xmlnss->end(); ++it )
581     {
582       if( (*it).second == xmlns )
583         return (*it).first;
584     }
585 
586     return EmptyString;
587   }
588 
findAttribute(const std::string & name) const589   const std::string& Tag::findAttribute( const std::string& name ) const
590   {
591     if( !m_attribs )
592       return EmptyString;
593 
594     AttributeList::const_iterator it = m_attribs->begin();
595     for( ; it != m_attribs->end(); ++it )
596       if( (*it)->name() == name )
597         return (*it)->value();
598 
599     return EmptyString;
600   }
601 
hasAttribute(const std::string & name,const std::string & value) const602   bool Tag::hasAttribute( const std::string& name, const std::string& value ) const
603   {
604     if( name.empty() || !m_attribs )
605       return false;
606 
607     AttributeList::const_iterator it = m_attribs->begin();
608     for( ; it != m_attribs->end(); ++it )
609       if( (*it)->name() == name )
610         return value.empty() || (*it)->value() == value;
611 
612     return false;
613   }
614 
hasChild(const std::string & name,const std::string & attr,const std::string & value) const615   bool Tag::hasChild( const std::string& name, const std::string& attr,
616                       const std::string& value ) const
617   {
618     if( attr.empty() )
619       return findChild( name ) ? true : false;
620     else
621       return findChild( name, attr, value ) ? true : false;
622   }
623 
findChild(const std::string & name) const624   Tag* Tag::findChild( const std::string& name ) const
625   {
626     if( !m_children )
627       return 0;
628 
629     TagList::const_iterator it = m_children->begin();
630     while( it != m_children->end() && (*it)->name() != name )
631       ++it;
632     return it != m_children->end() ? (*it) : 0;
633   }
634 
findChild(const std::string & name,const std::string & attr,const std::string & value) const635   Tag* Tag::findChild( const std::string& name, const std::string& attr,
636                        const std::string& value ) const
637   {
638     if( !m_children || name.empty() )
639       return 0;
640 
641     TagList::const_iterator it = m_children->begin();
642     while( it != m_children->end() && ( (*it)->name() != name || !(*it)->hasAttribute( attr, value ) ) )
643       ++it;
644     return it != m_children->end() ? (*it) : 0;
645   }
646 
hasChildWithCData(const std::string & name,const std::string & cdata) const647   bool Tag::hasChildWithCData( const std::string& name, const std::string& cdata ) const
648   {
649     if( !m_children || name.empty() || cdata.empty() )
650       return 0;
651 
652     TagList::const_iterator it = m_children->begin();
653     while( it != m_children->end() && ( (*it)->name() != name
654             || ( !cdata.empty() && (*it)->cdata() != cdata ) ) )
655       ++it;
656     return it != m_children->end();
657   }
658 
findChildWithAttrib(const std::string & attr,const std::string & value) const659   Tag* Tag::findChildWithAttrib( const std::string& attr, const std::string& value ) const
660   {
661     if( !m_children || attr.empty() )
662       return 0;
663 
664     TagList::const_iterator it = m_children->begin();
665     while( it != m_children->end() && !(*it)->hasAttribute( attr, value ) )
666       ++it;
667     return it != m_children->end() ? (*it) : 0;
668   }
669 
clone() const670   Tag* Tag::clone() const
671   {
672     Tag* t = new Tag( m_name );
673     t->m_xmlns = m_xmlns;
674     t->m_prefix = m_prefix;
675 
676     if( m_attribs )
677     {
678       t->m_attribs = new AttributeList();
679       Tag::AttributeList::const_iterator at = m_attribs->begin();
680       Attribute* attr;
681       for( ; at != m_attribs->end(); ++at )
682       {
683         attr = new Attribute( *(*at) );
684         attr->m_parent = t;
685         t->m_attribs->push_back( attr );
686       }
687     }
688 
689     if( m_xmlnss )
690     {
691       t->m_xmlnss = new StringMap( *m_xmlnss );
692     }
693 
694     if( m_nodes )
695     {
696       Tag::NodeList::const_iterator nt = m_nodes->begin();
697       for( ; nt != m_nodes->end(); ++nt )
698       {
699         switch( (*nt)->type )
700         {
701           case TypeTag:
702             t->addChild( (*nt)->tag->clone() );
703             break;
704           case TypeString:
705             t->addCData( *((*nt)->str) );
706             break;
707         }
708       }
709     }
710 
711     return t;
712   }
713 
findChildren(const std::string & name,const std::string & xmlns) const714   TagList Tag::findChildren( const std::string& name,
715                              const std::string& xmlns ) const
716   {
717     return m_children ? findChildren( *m_children, name, xmlns ) : TagList();
718   }
719 
findChildren(const TagList & list,const std::string & name,const std::string & xmlns) const720   TagList Tag::findChildren( const TagList& list, const std::string& name,
721                              const std::string& xmlns ) const
722   {
723     TagList ret;
724     TagList::const_iterator it = list.begin();
725     for( ; it != list.end(); ++it )
726     {
727       if( (*it)->name() == name && ( xmlns.empty() || (*it)->xmlns() == xmlns ) )
728         ret.push_back( (*it) );
729     }
730     return ret;
731   }
732 
removeChild(const std::string & name,const std::string & xmlns)733   void Tag::removeChild( const std::string& name, const std::string& xmlns )
734   {
735     if( name.empty() || !m_children || !m_nodes )
736       return;
737 
738     TagList l = findChildren( name, xmlns );
739     TagList::iterator it = l.begin();
740     TagList::iterator it2;
741     while( it != l.end() )
742     {
743       it2 = it++;
744       NodeList::iterator itn = m_nodes->begin();
745       for( ; itn != m_nodes->end(); ++itn )
746       {
747         if( (*itn)->type == TypeTag && (*itn)->tag == (*it2) )
748         {
749           delete (*itn);
750           m_nodes->erase( itn );
751           break;
752         }
753       }
754       m_children->remove( (*it2) );
755       delete (*it2);
756     }
757   }
758 
removeChild(Tag * tag)759   void Tag::removeChild( Tag* tag )
760   {
761     if( m_children )
762       m_children->remove( tag );
763 
764     if( !m_nodes )
765       return;
766 
767     NodeList::iterator it = m_nodes->begin();
768     for( ; it != m_nodes->end(); ++it )
769     {
770       if( (*it)->type == TypeTag && (*it)->tag == tag )
771       {
772         delete (*it);
773         m_nodes->erase( it );
774         return;
775       }
776     }
777   }
778 
removeAttribute(const std::string & attr,const std::string & value,const std::string & xmlns)779   void Tag::removeAttribute( const std::string& attr, const std::string& value,
780                              const std::string& xmlns )
781   {
782     if( attr.empty() || !m_attribs )
783       return;
784 
785     AttributeList::iterator it = m_attribs->begin();
786     AttributeList::iterator it2;
787     while( it != m_attribs->end() )
788     {
789       it2 = it++;
790       if( (*it2)->name() == attr && ( value.empty() || (*it2)->value() == value )
791                                  && ( xmlns.empty() || (*it2)->xmlns() == xmlns ) )
792       {
793         delete (*it2);
794         m_attribs->erase( it2 );
795       }
796     }
797   }
798 
findCData(const std::string & expression) const799   const std::string Tag::findCData( const std::string& expression ) const
800   {
801     const ConstTagList& l = findTagList( expression );
802     return !l.empty() ? l.front()->cdata() : EmptyString;
803   }
804 
findTag(const std::string & expression) const805   const Tag* Tag::findTag( const std::string& expression ) const
806   {
807     const ConstTagList& l = findTagList( expression );
808     return !l.empty() ? l.front() : 0;
809   }
810 
findTagList(const std::string & expression) const811   ConstTagList Tag::findTagList( const std::string& expression ) const
812   {
813     ConstTagList l;
814     if( expression == "/" || expression == "//" )
815       return l;
816 
817     if( m_parent && expression.length() >= 2 && expression[0] == '/'
818                                              && expression[1] != '/' )
819       return m_parent->findTagList( expression );
820 
821     unsigned len = 0;
822     Tag* p = parse( expression, len );
823 //     if( p )
824 //       printf( "parsed tree: %s\n", p->xml().c_str() );
825     l = evaluateTagList( p );
826     delete p;
827     return l;
828   }
829 
evaluateTagList(Tag * token) const830   ConstTagList Tag::evaluateTagList( Tag* token ) const
831   {
832     ConstTagList result;
833     if( !token )
834       return result;
835 
836 //     printf( "evaluateTagList called in Tag %s and Token %s (type: %s)\n", name().c_str(),
837 //             token->name().c_str(), token->findAttribute( TYPE ).c_str() );
838 
839     TokenType tokenType = static_cast<TokenType>( atoi( token->findAttribute( TYPE ).c_str() ) );
840     switch( tokenType )
841     {
842       case XTUnion:
843         add( result, evaluateUnion( token ) );
844         break;
845       case XTElement:
846       {
847 //         printf( "in XTElement, token: %s\n", token->name().c_str() );
848         if( token->name() == name() || token->name() == "*" )
849         {
850 //           printf( "found %s\n", name().c_str() );
851           const TagList& tokenChildren = token->children();
852           if( tokenChildren.size() )
853           {
854             bool predicatesSucceeded = true;
855             TagList::const_iterator cit = tokenChildren.begin();
856             for( ; cit != tokenChildren.end(); ++cit )
857             {
858               if( (*cit)->hasAttribute( "predicate", "true" ) )
859               {
860                 predicatesSucceeded = evaluatePredicate( (*cit) );
861                 if( !predicatesSucceeded )
862                   return result;
863               }
864             }
865 
866             bool hasElementChildren = false;
867             cit = tokenChildren.begin();
868             for( ; cit != tokenChildren.end(); ++cit )
869             {
870               if( (*cit)->hasAttribute( "predicate", "true" ) ||
871                   (*cit)->hasAttribute( "number", "true" ) )
872                 continue;
873 
874               hasElementChildren = true;
875 
876 //               printf( "checking %d children of token %s\n", tokenChildren.size(), token->name().c_str() );
877               if( m_children && !m_children->empty() )
878               {
879                 TagList::const_iterator it = m_children->begin();
880                 for( ; it != m_children->end(); ++it )
881                 {
882                   add( result, (*it)->evaluateTagList( (*cit) ) );
883                 }
884               }
885               else if( atoi( (*cit)->findAttribute( TYPE ).c_str() ) == XTDoubleDot && m_parent )
886               {
887                 (*cit)->addAttribute( TYPE, XTDot );
888                 add( result, m_parent->evaluateTagList( (*cit) ) );
889               }
890             }
891 
892             if( !hasElementChildren )
893               result.push_back( this );
894           }
895           else
896           {
897 //             printf( "adding %s to result set\n", name().c_str() );
898             result.push_back( this );
899           }
900         }
901 //         else
902 //           printf( "found %s != %s\n", token->name().c_str(), name().c_str() );
903 
904         break;
905       }
906       case XTDoubleSlash:
907       {
908 //         printf( "in XTDoubleSlash\n" );
909         Tag* t = token->clone();
910 //         printf( "original token: %s\ncloned token: %s\n", token->xml().c_str(), n->xml().c_str() );
911         t->addAttribute( TYPE, XTElement );
912         add( result, evaluateTagList( t ) );
913         const ConstTagList& res2 = allDescendants();
914         ConstTagList::const_iterator it = res2.begin();
915         for( ; it != res2.end(); ++it )
916         {
917           add( result, (*it)->evaluateTagList( t ) );
918         }
919         delete t;
920         break;
921       }
922       case XTDot:
923       {
924         const TagList& tokenChildren = token->children();
925         if( !tokenChildren.empty() )
926         {
927           add( result, evaluateTagList( tokenChildren.front() ) );
928         }
929         else
930           result.push_back( this );
931         break;
932       }
933       case XTDoubleDot:
934       {
935 //         printf( "in XTDoubleDot\n" );
936         if( m_parent )
937         {
938           const TagList& tokenChildren = token->children();
939           if( tokenChildren.size() )
940           {
941             Tag* testtoken = tokenChildren.front();
942             if( testtoken->name() == "*" )
943             {
944               add( result, m_parent->evaluateTagList( testtoken ) );
945             }
946             else
947             {
948               Tag* t = token->clone();
949               t->addAttribute( TYPE, XTElement );
950               t->m_name = m_parent->m_name;
951               add( result, m_parent->evaluateTagList( t ) );
952               delete t;
953             }
954           }
955           else
956           {
957             result.push_back( m_parent );
958           }
959         }
960       }
961       case XTInteger:
962       {
963         const TagList& l = token->children();
964         if( !l.size() )
965           break;
966 
967         const ConstTagList& res = evaluateTagList( l.front() );
968 
969         int pos = atoi( token->name().c_str() );
970 //         printf( "checking index %d\n", pos );
971         if( pos > 0 && pos <= static_cast<int>( res.size() ) )
972         {
973           ConstTagList::const_iterator it = res.begin();
974           while ( --pos )
975           {
976             ++it;
977           }
978           result.push_back( *it );
979         }
980         break;
981       }
982       default:
983         break;
984     }
985     return result;
986   }
987 
evaluateBoolean(Tag * token) const988   bool Tag::evaluateBoolean( Tag* token ) const
989   {
990     if( !token )
991       return false;
992 
993     bool result = false;
994     TokenType tokenType = static_cast<TokenType>( atoi( token->findAttribute( TYPE ).c_str() ) );
995     switch( tokenType )
996     {
997       case XTAttribute:
998         if( token->name() == "*" && m_attribs && m_attribs->size() )
999           result = true;
1000         else
1001           result = hasAttribute( token->name() );
1002         break;
1003       case XTOperatorEq:
1004         result = evaluateEquals( token );
1005         break;
1006       case XTOperatorLt:
1007         break;
1008       case XTOperatorLtEq:
1009         break;
1010       case XTOperatorGtEq:
1011         break;
1012       case XTOperatorGt:
1013         break;
1014       case XTUnion:
1015       case XTElement:
1016       {
1017         Tag* t = new Tag( "." );
1018         t->addAttribute( TYPE, XTDot );
1019         t->addChild( token );
1020         result = !evaluateTagList( t ).empty();
1021         t->removeChild( token );
1022         delete t;
1023         break;
1024       }
1025       default:
1026         break;
1027     }
1028 
1029     return result;
1030   }
1031 
evaluateEquals(Tag * token) const1032   bool Tag::evaluateEquals( Tag* token ) const
1033   {
1034     if( !token || token->children().size() != 2 )
1035       return false;
1036 
1037     bool result = false;
1038     TagList::const_iterator it = token->children().begin();
1039     Tag* ch1 = (*it);
1040     Tag* ch2 = (*++it);
1041 
1042     TokenType tt1 = static_cast<TokenType>( atoi( ch1->findAttribute( TYPE ).c_str() ) );
1043     TokenType tt2 = static_cast<TokenType>( atoi( ch2->findAttribute( TYPE ).c_str() ) );
1044     switch( tt1 )
1045     {
1046       case XTAttribute:
1047         switch( tt2 )
1048         {
1049           case XTInteger:
1050           case XTLiteral:
1051             result = ( findAttribute( ch1->name() ) == ch2->name() );
1052             break;
1053           case XTAttribute:
1054             result = ( hasAttribute( ch1->name() ) && hasAttribute( ch2->name() ) &&
1055                       findAttribute( ch1->name() ) == findAttribute( ch2->name() ) );
1056             break;
1057           default:
1058             break;
1059         }
1060         break;
1061       case XTInteger:
1062       case XTLiteral:
1063         switch( tt2 )
1064         {
1065           case XTAttribute:
1066             result = ( ch1->name() == findAttribute( ch2->name() ) );
1067             break;
1068           case XTLiteral:
1069           case XTInteger:
1070             result = ( ch1->name() == ch2->name() );
1071             break;
1072           default:
1073             break;
1074         }
1075         break;
1076       default:
1077         break;
1078     }
1079 
1080     return result;
1081   }
1082 
allDescendants() const1083   ConstTagList Tag::allDescendants() const
1084   {
1085     ConstTagList result;
1086 
1087     if( !m_children )
1088       return result;
1089 
1090     TagList::const_iterator it = m_children->begin();
1091     for( ; it != m_children->end(); ++it )
1092     {
1093       result.push_back( (*it) );
1094       add( result, (*it)->allDescendants() );
1095     }
1096     return result;
1097   }
1098 
evaluateUnion(Tag * token) const1099   ConstTagList Tag::evaluateUnion( Tag* token ) const
1100   {
1101     ConstTagList result;
1102     if( !token )
1103       return result;
1104 
1105     const TagList& l = token->children();
1106     TagList::const_iterator it = l.begin();
1107     for( ; it != l.end(); ++it )
1108     {
1109       add( result, evaluateTagList( (*it) ) );
1110     }
1111     return result;
1112   }
1113 
closePreviousToken(Tag ** root,Tag ** current,Tag::TokenType & type,std::string & tok) const1114   void Tag::closePreviousToken( Tag** root, Tag** current, Tag::TokenType& type, std::string& tok ) const
1115   {
1116     if( !tok.empty() )
1117     {
1118       addToken( root, current, type, tok );
1119       type = XTElement;
1120       tok = EmptyString;
1121     }
1122   }
1123 
parse(const std::string & expression,unsigned & len,Tag::TokenType border) const1124   Tag* Tag::parse( const std::string& expression, unsigned& len, Tag::TokenType border ) const
1125   {
1126     Tag* root = 0;
1127     Tag* current = root;
1128     std::string token;
1129 
1130 //     XPathError error = XPNoError;
1131 //     XPathState state = Init;
1132 //     int expected = 0;
1133 //     bool run = true;
1134 //     bool ws = false;
1135 
1136     Tag::TokenType type  = XTElement;
1137 
1138     char c;
1139     for( ; len < expression.length(); ++len )
1140     {
1141       c = expression[len];
1142       if( type == XTLiteralInside && c != '\'' )
1143       {
1144         token += c;
1145         continue;
1146       }
1147 
1148       switch( c )
1149       {
1150         case '/':
1151           closePreviousToken( &root, &current, type, token );
1152 
1153           if( len < expression.length()-1 && expression[len+1] == '/' )
1154           {
1155 //             addToken( &root, &current, XTDoubleSlash, "//" );
1156             type = XTDoubleSlash;
1157             ++len;
1158           }
1159 //           else
1160 //           {
1161 //             if( !current )
1162 //             addToken( &root, &current, XTSlash, "/" );
1163 //           }
1164           break;
1165         case ']':
1166           closePreviousToken( &root, &current, type, token );
1167           return root;
1168         case '[':
1169         {
1170           closePreviousToken( &root, &current, type, token );
1171           Tag* t = parse( expression, ++len, XTRightBracket );
1172           if( !addPredicate( &root, &current, t ) )
1173             delete t;
1174           break;
1175         }
1176         case '(':
1177         {
1178           closePreviousToken( &root, &current, type, token );
1179           Tag* t = parse( expression, ++len, XTRightParenthesis );
1180           if( current )
1181           {
1182 //             printf( "added %s to %s\n", t->xml().c_str(), current->xml().c_str() );
1183             t->addAttribute( "argument", "true" );
1184             current->addChild( t );
1185           }
1186           else
1187           {
1188             root = t;
1189 //             printf( "made %s new root\n", t->xml().c_str() );
1190           }
1191           break;
1192         }
1193         case ')':
1194           closePreviousToken( &root, &current, type, token );
1195           ++len;
1196           return root;
1197         case '\'':
1198           if( type == XTLiteralInside )
1199             if( expression[len - 2] == '\\' )
1200               token[token.length() - 2] = c;
1201             else
1202               type = XTLiteral;
1203           else
1204             type = XTLiteralInside;
1205           break;
1206         case '@':
1207           type = XTAttribute;
1208           break;
1209         case '.':
1210           token += c;
1211           if( token.size() == 1 )
1212           {
1213             if( len < expression.length()-1 && expression[len+1] == '.' )
1214             {
1215               type = XTDoubleDot;
1216               ++len;
1217               token += c;
1218             }
1219             else
1220             {
1221               type = XTDot;
1222             }
1223           }
1224           break;
1225         case '*':
1226 //           if( !root || ( current && ( current->tokenType() == XTSlash
1227 //                                       || current->tokenType() == XTDoubleSlash ) ) )
1228 //           {
1229 //             addToken( &root, &current, type, "*" );
1230 //             break;
1231 //           }
1232           addToken( &root, &current, type, "*" );
1233           type = XTElement;
1234           break;
1235         case '+':
1236         case '>':
1237         case '<':
1238         case '=':
1239         case '|':
1240         {
1241           closePreviousToken( &root, &current, type, token );
1242           std::string s( 1, c );
1243           Tag::TokenType ttype = getType( s );
1244           if( ttype <= border )
1245             return root;
1246           Tag* t = parse( expression, ++len, ttype );
1247           addOperator( &root, &current, t, ttype, s );
1248           if( border == XTRightBracket )
1249             return root;
1250           break;
1251         }
1252         default:
1253           token += c;
1254       }
1255     }
1256 
1257     if( !token.empty() )
1258       addToken( &root, &current, type, token );
1259 
1260 //     if( error != XPNoError )
1261 //       printf( "error: %d\n", error );
1262     return root;
1263   }
1264 
addToken(Tag ** root,Tag ** current,Tag::TokenType type,const std::string & token) const1265   void Tag::addToken( Tag **root, Tag **current, Tag::TokenType type,
1266                       const std::string& token ) const
1267   {
1268     Tag* t = new Tag( token );
1269     if( t->isNumber() && !t->children().size() )
1270       type = XTInteger;
1271     t->addAttribute( TYPE, type );
1272 
1273     if( *root )
1274     {
1275 //       printf( "new current %s, type: %d\n", token.c_str(), type );
1276       (*current)->addChild( t );
1277       *current = t;
1278     }
1279     else
1280     {
1281 //       printf( "new root %s, type: %d\n", token.c_str(), type );
1282       *current = *root = t;
1283     }
1284   }
1285 
addOperator(Tag ** root,Tag ** current,Tag * arg,Tag::TokenType type,const std::string & token) const1286   void Tag::addOperator( Tag** root, Tag** current, Tag* arg,
1287                            Tag::TokenType type, const std::string& token ) const
1288   {
1289     Tag* t = new Tag( token );
1290     t->addAttribute( TYPE, type );
1291 //     printf( "new operator: %s (arg1: %s, arg2: %s)\n", t->name().c_str(), (*root)->xml().c_str(),
1292 //                                                                           arg->xml().c_str() );
1293     t->addAttribute( "operator", "true" );
1294     t->addChild( *root );
1295     t->addChild( arg );
1296     *current = *root = t;
1297   }
1298 
addPredicate(Tag ** root,Tag ** current,Tag * token) const1299   bool Tag::addPredicate( Tag **root, Tag **current, Tag* token ) const
1300   {
1301     if( !*root || !*current )
1302       return false;
1303 
1304     if( ( token->isNumber() && !token->children().size() ) || token->name() == "+" )
1305     {
1306 //       printf( "found Index %s, full: %s\n", token->name().c_str(), token->xml().c_str() );
1307       if( !token->hasAttribute( "operator", "true" ) )
1308       {
1309         token->addAttribute( TYPE, XTInteger );
1310       }
1311       if( *root == *current )
1312       {
1313         *root = token;
1314 //         printf( "made Index new root\n" );
1315       }
1316       else
1317       {
1318         (*root)->removeChild( *current );
1319         (*root)->addChild( token );
1320 //         printf( "added Index somewhere between root and current\n" );
1321       }
1322       token->addChild( *current );
1323 //       printf( "added Index %s, full: %s\n", token->name().c_str(), token->xml().c_str() );
1324     }
1325     else
1326     {
1327       token->addAttribute( "predicate", "true" );
1328       (*current)->addChild( token );
1329     }
1330 
1331     return true;
1332   }
1333 
getType(const std::string & c)1334   Tag::TokenType Tag::getType( const std::string& c )
1335   {
1336     if( c == "|" )
1337       return XTUnion;
1338     if( c == "<" )
1339       return XTOperatorLt;
1340     if( c == ">" )
1341       return XTOperatorGt;
1342     if( c == "*" )
1343       return XTOperatorMul;
1344     if( c == "+" )
1345       return XTOperatorPlus;
1346     if( c == "=" )
1347       return XTOperatorEq;
1348 
1349     return XTNone;
1350   }
1351 
isWhitespace(const char c)1352   bool Tag::isWhitespace( const char c )
1353   {
1354     return ( c == 0x09 || c == 0x0a || c == 0x0d || c == 0x20 );
1355   }
1356 
isNumber() const1357   bool Tag::isNumber() const
1358   {
1359     if( m_name.empty() )
1360       return false;
1361 
1362     std::string::size_type l = m_name.length();
1363     std::string::size_type i = 0;
1364     while( i < l && isdigit( m_name[i] ) )
1365       ++i;
1366     return i == l;
1367   }
1368 
add(ConstTagList & one,const ConstTagList & two)1369   void Tag::add( ConstTagList& one, const ConstTagList& two )
1370   {
1371     ConstTagList::const_iterator it = two.begin();
1372     for( ; it != two.end(); ++it )
1373       if( std::find( one.begin(), one.end(), (*it) ) == one.end() )
1374         one.push_back( (*it) );
1375   }
1376 
1377 }
1378