xmlpathautomaton.hpp

Go to the documentation of this file.

/*
 * Copyright (c) 2014 Patrick P. Frey
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

#ifndef __TEXTWOLF_XML_PATH_AUTOMATON_HPP__
#define __TEXTWOLF_XML_PATH_AUTOMATON_HPP__
#include "textwolf/char.hpp"
#include "textwolf/charset.hpp"
#include "textwolf/exception.hpp"
#include "textwolf/xmlscanner.hpp"
#include "textwolf/staticbuffer.hpp"
#include <limits>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <cstddef>
#include <stdexcept>

namespace textwolf {

template <class CharSet_=charset::UTF8>
class XMLPathSelectAutomaton :public throws_exception
{
public:
        XMLPathSelectAutomaton()
        {}

        typedef CharSet_ CharSet;
        typedef int Hash;
        typedef XMLPathSelectAutomaton<CharSet> ThisXMLPathSelectAutomaton;

        virtual ~XMLPathSelectAutomaton(){}

public:
        enum Operation
        {
                Content,                        //< searching content token
                OpenTag,                        //< searching an open tag
                CloseTag,                       //< searching a close tag
                Attribute,                      //< searching an attribute
                ThisAttributeValue,             //< checking the value of the attribute just parsed (not an arbitrary but this one)
                AttributeValue,                 //< searching a value of an attribute
                ContentStart                    //< looking for the start of content (to signal the end of the XML header)
        };

        static const char* operationName( Operation op)
        {
                static const char* name[ 7] = {"Content", "OpenTag", "CloseTag", "Attribute", "ThisAttributeValue", "AttributeValue", "ContentStart"};
                return name[ (unsigned int)op];
        }

        struct Mask
        {
                unsigned short pos;                     //< positively selected elements bitmask
                unsigned short neg;                     //< negatively selected elements bitmask that determines when a search pattern is given up copletely

                bool empty() const                                                              {return (pos==0);}

                Mask( unsigned short p_pos=0, unsigned short p_neg=0):pos(p_pos),neg(p_neg) {}

                Mask( const Mask& orig)                                                         :pos(orig.pos),neg(orig.neg) {}

                void reset()                                                                    {pos=0; neg=0;}

                void reject( XMLScannerBase::ElementType e)                                     {neg |= (1<<(unsigned short)e);}
                bool hasReject( XMLScannerBase::ElementType e) const                            {return (neg & (1<<(unsigned short)e)) != 0;}

                void match( XMLScannerBase::ElementType e)                                      {pos |= (1<<(unsigned short)e);}
                bool hasMatch( XMLScannerBase::ElementType e) const                             {return (pos & (1<<(unsigned short)e)) != 0;}

                bool operator==( const Mask& o)
                {
                        return (o.pos == pos) && (o.neg == neg);
                }

                void seekop( Operation op)
                {
                        switch (op)
                        {
                                case OpenTag:
                                        this->match( XMLScannerBase::OpenTag);
                                        this->match( XMLScannerBase::HeaderStart);
                                        break;
                                case CloseTag:
                                        this->match( XMLScannerBase::CloseTag);
                                        this->match( XMLScannerBase::CloseTagIm);
                                        this->match( XMLScannerBase::HeaderEnd);
                                        break;
                                case Attribute:
                                        this->match( XMLScannerBase::TagAttribName);
                                        this->match( XMLScannerBase::HeaderAttribName);
                                        this->reject( XMLScannerBase::Content);
                                        break;
                                case ThisAttributeValue:
                                        this->match( XMLScannerBase::TagAttribValue);
                                        this->match( XMLScannerBase::HeaderAttribValue);
                                        this->reject( XMLScannerBase::TagAttribName);
                                        this->reject( XMLScannerBase::HeaderAttribName);
                                        this->reject( XMLScannerBase::Content);
                                        this->reject( XMLScannerBase::OpenTag);
                                        break;
                                case AttributeValue:
                                        this->match( XMLScannerBase::TagAttribValue);
                                        this->match( XMLScannerBase::HeaderAttribValue);
                                        this->reject( XMLScannerBase::Content);
                                        break;
                                case Content:
                                        this->match( XMLScannerBase::Content);
                                        break;
                                case ContentStart:
                                        this->match( XMLScannerBase::HeaderEnd);
                                        break;
                        }
                }

                const char* seekopName() const
                {
                        if (this->hasMatch( XMLScannerBase::OpenTag)
                        &&  this->hasMatch( XMLScannerBase::HeaderStart))
                                return "OpenTag";

                        if (this->hasMatch( XMLScannerBase::CloseTag)
                        &&  this->hasMatch( XMLScannerBase::CloseTagIm)
                        &&  this->hasMatch( XMLScannerBase::HeaderEnd))
                                return "CloseTag";

                        if (this->hasMatch( XMLScannerBase::TagAttribName)
                        &&  this->hasMatch( XMLScannerBase::HeaderAttribName)
                        &&  this->hasReject( XMLScannerBase::Content))
                                return "Attribute";

                        if (this->hasMatch( XMLScannerBase::TagAttribValue)
                        &&  this->hasMatch( XMLScannerBase::HeaderAttribValue)
                        &&  this->hasReject( XMLScannerBase::Content))
                                return "AttributeValue";

                        if (this->hasMatch( XMLScannerBase::TagAttribValue)
                        &&  this->hasMatch( XMLScannerBase::HeaderAttribValue)
                        &&  this->hasReject( XMLScannerBase::TagAttribName)
                        &&  this->hasReject( XMLScannerBase::HeaderAttribName)
                        &&  this->hasReject( XMLScannerBase::Content)
                        &&  this->hasReject( XMLScannerBase::OpenTag))
                                return "ThisAttributeValue";

                        if (this->hasMatch( XMLScannerBase::Content))
                                return "Content";

                        if (this->hasMatch( XMLScannerBase::HeaderEnd))
                                return "ContentStart";

                        if (pos == 0 && neg == 0)
                                return "None";

                        return "";
                }

                void join( const Mask& mask)                            {pos |= mask.pos; neg |= mask.neg;}

                bool matches( XMLScannerBase::ElementType e) const      {return (0 != (pos & (1<<(unsigned short)e)));}

                bool rejects( XMLScannerBase::ElementType e) const      {return (0 != (neg & (1<<(unsigned short)e)));}
        };

        struct Core
        {
                Mask mask;                      //< mask definiting what tokens are matching this state
                bool follow;                    //< true, if the state is seeking tokens in all follow scopes in the XML tree
                int typeidx;                    //< type of the element emitted by this state on a match
                int cnt_start;                  //< lower bound of the element index matching (for index ranges)
                int cnt_end;                    //< upper bound of the element index matching (for index ranges)

                Core()                  :follow(false),typeidx(0),cnt_start(0),cnt_end(-1) {}
                Core( const Core& o)    :mask(o.mask),follow(o.follow),typeidx(o.typeidx),cnt_start(o.cnt_start),cnt_end(o.cnt_end) {}
        };

        struct State
        {
                Core core;                      //< core of the state (the part used in processing)
                unsigned int keysize;           //< key size of the element
                char* key;                      //< key of the element
                char* srckey;                   //< key of the element as in source (for debugging or reporting, etc.)
                int next;                       //< follow state
                int link;                       //< alternative state to check

                State()
                        :keysize(0),key(0),srckey(0),next(-1),link(-1) {}

                State( const State& orig)
                        :core(orig.core),keysize(orig.keysize),key(0),srckey(0),next(orig.next),link(orig.link)
                {
                        defineKey( orig.keysize, orig.key, orig.srckey);
                }

                ~State()
                {
                        if (key) delete [] key;
                        if (srckey) delete [] srckey;
                }

                bool isempty()                          {return key==0&&core.typeidx==0&&next==0&&link==0&&core.mask.empty();}

                void defineKey( unsigned int p_keysize, const char* p_key, const char* p_srckey)
                {
                        unsigned int ii;
                        if (key)
                        {
                                delete [] key;
                                key = 0;
                        }
                        if (srckey)
                        {
                                delete [] srckey;
                                srckey = 0;
                        }
                        if (p_key)
                        {
                                key = new char[ keysize=p_keysize];
                                for (ii=0; ii<keysize; ii++) key[ii]=p_key[ii];
                        }
                        if (p_srckey)
                        {
                                for (ii=0; p_srckey[ii]!=0; ii++);
                                srckey = new char[ ii+1];
                                for (ii=0; p_srckey[ii]!=0; ii++) srckey[ii]=p_srckey[ii];
                                srckey[ ii] = 0;
                        }
                }

                void defineNext( Operation op, unsigned int p_keysize, const char* p_key, const char* p_srckey, int p_next, bool p_follow=false)
                {
                        core.mask.seekop( op);
                        defineKey( p_keysize, p_key, p_srckey);
                        next = p_next;
                        core.follow = p_follow;
                }

                void defineOutput( const Mask& mask, int p_typeidx, bool p_follow, int p_start, int p_end)
                {
                        core.mask = mask;
                        core.typeidx = p_typeidx;
                        core.cnt_end = p_end;
                        core.cnt_start = p_start;
                        core.follow = p_follow;
                }

                void defLink( int p_link)
                {
                        link = p_link;
                }

                std::string tostring() const
                {
                        std::ostringstream rt;
                        if (next >= 0) rt << " ->" << next;
                        if (link >= 0) rt << " ~" << link;
                        rt << ' ';
                        if (core.follow)
                        {
                                rt << '/';
                        }
                        rt << '/';
                        rt << core.mask.seekopName();
                        if (srckey)
                        {
                                rt << " '" << srckey << "'";
                        }
                        else
                        {
                                rt << " (null)";
                        }
                        if (core.cnt_end > 0)
                        {
                                rt << '[' << core.cnt_start << ',' << rt << core.cnt_end << ']';
                        }
                        if (core.typeidx)
                        {
                                rt << " =>" << core.typeidx;
                        }
                        return rt.str();
                }
        };
        std::vector<State> states;                              //< the states of the statemachine

        std::string tostring() const
        {
                std::ostringstream rt;
                typename std::vector<State>::const_iterator ii=states.begin(), ee=states.end();
                for (; ii != ee; ++ii)
                {
                        rt << (int)(ii-states.begin()) << ": " << ii->tostring() << std::endl;
                }
                return rt.str();
        }

        template <class Buffer>
        void getEmmitedTokens( unsigned int stateidx, XMLScannerBase::ElementType e, Buffer& buf) const
        {
                int si = states[ stateidx].next;
                while (si >= 0)
                {
                        if (states[ si].core.typeidx && states[ si].core.mask.matches( e))
                        {
                                buf.push_back( states[ si].core.typeidx);
                        }
                        si = states[ si].link;
                }
        }

        struct Token
        {
                Core core;                                      //< core of the state
                int stateidx;                                   //< index into the automaton, poiting to the state

                Token()                                         :stateidx(-1) {}
                Token( const Token& orig)                       :core(orig.core),stateidx(orig.stateidx) {}
                Token( const State& state, int p_stateidx)      :core(state.core),stateidx(p_stateidx) {}
        };

        struct Scope
        {
                Mask mask;                                      //< joined mask of all tokens active in this scope
                Mask followMask;                                //< joined mask of all tokens active in this and all sub scopes of this scope

                struct Range
                {
                        unsigned int tokenidx_from;             //< lower bound token index
                        unsigned int tokenidx_to;               //< upper bound token index
                        unsigned int followidx;                 //< pointer to follow token stack with tokens active in this and all sub scopes of this scope

                        Range()                         :tokenidx_from(0),tokenidx_to(0),followidx(0) {}
                        Range( const Scope& orig)       :tokenidx_from(orig.tokenidx_from),tokenidx_to(orig.tokenidx_to),followidx(orig.followidx) {}
                };
                Range range;                                                    //< valid (active) token range of this scope (on the token stacks)

                Scope( const Scope& orig)               :mask(orig.mask),followMask(orig.followMask),range(orig.range) {}
                Scope& operator =( const Scope& orig)   {mask=orig.mask; followMask=orig.followMask; range=orig.range; return *this;}
                Scope()                                 {}
        };

private:
        int defineNext( int stateidx, Operation op, unsigned int keysize, const char* key, const char* srckey, bool follow=false) throw(exception,std::bad_alloc)
        {
                try
                {
                        State state;
                        if (states.size() == 0)
                        {
                                stateidx = states.size();
                                states.push_back( state);
                        }
                        Mask mask;
                        mask.seekop( op);

                        for (int ee=stateidx; ee != -1; stateidx=ee,ee=states[ee].link)
                        {
                                if ((states[ee].key != 0) && (keysize == states[ee].keysize) && (states[ee].core.follow == follow) && (mask == states[ee].core.mask))
                                {
                                        unsigned int ii;
                                        for (ii=0; ii<keysize && states[ee].key[ii]==key[ii]; ii++);
                                        if (ii == keysize) return states[ee].next;
                                }
                        }
                        if (!states[ stateidx].isempty())
                        {
                                while (states[ stateidx].link >= 0)
                                {
                                        stateidx = states[ stateidx].link;
                                }
                                states[ stateidx].link = states.size();
                                stateidx = states.size();
                                states.push_back( state);
                        }
                        states.push_back( state);
                        unsigned int lastidx = states.size()-1;
                        states[ stateidx].defineNext( op, keysize, key, srckey, lastidx, follow);
                        return stateidx=lastidx;
                }
                catch (std::bad_alloc)
                {
                        throw exception( OutOfMem);
                }
                catch (...)
                {
                        throw exception( Unknown);
                }
        }

        int defineOutput( int stateidx, const Mask& printOpMask, int typeidx, bool follow, int start, int end) throw(exception,std::bad_alloc)
        {
                try
                {
                        State state;
                        if (states.size() == 0)
                        {
                                stateidx = states.size();
                                states.push_back( state);
                        }
                        if ((unsigned int)stateidx >= states.size()) throw exception( IllegalParam);

                        if (!states[stateidx].isempty())
                        {
                                while (states[ stateidx].link >= 0)
                                {
                                        stateidx = states[stateidx].link;
                                }
                                states[ stateidx].link = states.size();
                                stateidx = states.size();
                                states.push_back( state);
                                
                        }
                        states[ stateidx].defineOutput( printOpMask, typeidx, follow, start, end);
                        return stateidx;
                }
                catch (std::bad_alloc)
                {
                        throw exception( OutOfMem);
                }
                catch (...)
                {
                        throw exception( Unknown);
                }
        }

public:
        struct PathElement :throws_exception
        {
        private:
                XMLPathSelectAutomaton* xs;             //< XML Path select automaton where this node is an element of
                int stateidx;                           //< state of this element in the automaton

                struct Range
                {
                        int start;                      //< index of starting element starting with 0
                        int end;                        //< index of upper boundary element (not belonging to range anymore). -1 if undefined (unlimited)

                        Range( const Range& o)          :start(o.start),end(o.end){}
                        Range( int p_start, int p_end)  :start(p_start),end(p_end){}
                        Range( int count)               :start(0),end(count){}
                        Range()                         :start(0),end(-1){}
                };
                Range range;                    //< Index range of this XML path element
                bool follow;                    //< true, if this element is active (firing) for all sub scopes of the activation scope
                Mask pushOpMask;                //< mask for firing element actions
                Mask printOpMask;               //< mask for printing element actions

        private:
                PathElement& defineOutput( Operation op)
                {
                        printOpMask.reset();
                        printOpMask.seekop( op);
                        return *this;
                }

                PathElement& doSelect( Operation op, const char* value) throw(exception,std::bad_alloc)
                {
                        static XMLScannerBase::IsTagCharMap isTagCharMap;
                        if (xs != 0)
                        {
                                if (value)
                                {
                                        char buf[ 1024];
                                        StaticBuffer pb( buf, sizeof(buf));
                                        char* itr = const_cast<char*>(value);
                                        typedef XMLScanner<char*,CharSet,CharSet,StaticBuffer> StaticXMLScanner;
                                        if (!StaticXMLScanner::parseStaticToken( isTagCharMap, itr, pb))
                                        {
                                                throw exception( IllegalAttributeName);
                                        }
                                        stateidx = xs->defineNext( stateidx, op, pb.size(), pb.ptr(), value, follow);
                                }
                                else
                                {
                                        stateidx = xs->defineNext( stateidx, op, 0, 0, 0, follow);
                                }
                        }
                        return *this;
                }

                PathElement& doFollow()
                {
                        follow = true;
                        return *this;
                }

                PathElement& doRange( int p_start, int p_end)
                {
                        if (range.end == -1)
                        {
                                range = Range( p_start, p_end);
                        }
                        else if (p_end < range.end)
                        {
                                range.end = p_end;
                        }
                        else if (p_start > range.start)
                        {
                                range.start = p_start;
                        }
                        return *this;
                }

                PathElement& doCount( int p_count)
                {
                        return doRange( 0, p_count);
                }

                PathElement& doStart( int p_start)
                {
                        return doRange( p_start, std::numeric_limits<int>::max());
                }

                PathElement& push( int typeidx) throw(exception,std::bad_alloc)
                {
                        if (xs != 0) stateidx = xs->defineOutput( stateidx, printOpMask, typeidx, follow, range.start, range.end);
                        return *this;
                }

        public:
                PathElement()                                                   :xs(0),stateidx(0),follow(false),pushOpMask(0),printOpMask(0){}
                PathElement( XMLPathSelectAutomaton* p_xs, int p_si=0)          :xs(p_xs),stateidx(p_si),follow(false),pushOpMask(0),printOpMask(0){}
                PathElement( const PathElement& orig)                           :xs(orig.xs),stateidx(orig.stateidx),range(orig.range),follow(orig.follow),pushOpMask(orig.pushOpMask),printOpMask(orig.printOpMask) {}

                PathElement& operator --(int)                                                   {return doFollow();}
                PathElement& operator []( const char* name) throw(exception,std::bad_alloc)     {return doSelect( OpenTag, name);}
                PathElement& selectTag( const char* name) throw(exception,std::bad_alloc)       {return doSelect( OpenTag, name);}
                PathElement& selectCloseTag() throw(exception,std::bad_alloc)                   {return doSelect( CloseTag, 0);}

                PathElement& operator ()( const char* name) throw(exception,std::bad_alloc)     {return doSelect( Attribute, name).defineOutput( ThisAttributeValue);}
                PathElement& selectAttribute( const char* name) throw(exception,std::bad_alloc) {return doSelect( Attribute, name).defineOutput( ThisAttributeValue);}

                PathElement& operator ()( const char* name, const char* value) throw(exception,std::bad_alloc)  {return doSelect( Attribute, name).doSelect( ThisAttributeValue, value);}

                PathElement& ifAttribute( const char* name, const char* value) throw(exception,std::bad_alloc)  {return doSelect( Attribute, name).doSelect( ThisAttributeValue, value);}

                PathElement& TO(int idx) throw(exception,std::bad_alloc)                        {return doCount((idx>=0)?(idx+1):-1);}
                PathElement& FROM(int idx) throw(exception,std::bad_alloc)                      {return doStart(idx); return *this;}
                PathElement& RANGE(int idx1, int idx2) throw(exception,std::bad_alloc)          {return doRange(idx1,(idx2>=0)?(idx2+1):-1); return *this;}
                PathElement& INDEX(int idx) throw(exception,std::bad_alloc)                     {return doRange(idx,idx+1); return *this;}

                PathElement& operator =(int type) throw(exception,std::bad_alloc)               {return push( type);}
                PathElement& assignType(int type) throw(exception,std::bad_alloc)               {return push( type);}

                PathElement& operator ()()  throw(exception,std::bad_alloc)                     {return defineOutput(Content);}
                PathElement& selectContent()  throw(exception,std::bad_alloc)                   {return defineOutput(Content);}
        };

        PathElement operator*()
        {
                return PathElement( this);
        }
};

} //namespace
#endif