xmlpathselect.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_SELECT_HPP__
#define __TEXTWOLF_XML_PATH_SELECT_HPP__
#include "textwolf/char.hpp"
#include "textwolf/charset_interface.hpp"
#include "textwolf/exception.hpp"
#include "textwolf/xmlscanner.hpp"
#include "textwolf/staticbuffer.hpp"
#include "textwolf/xmlpathautomaton.hpp"
#include <limits>
#include <string>
#include <vector>
#include <map>
#include <cstddef>

namespace textwolf {

template <typename Element>
class DefaultStackType
        :public std::vector<Element>
{
public:
        DefaultStackType(){}
        DefaultStackType( const DefaultStackType& o)
                :std::vector<Element>(o){}
};

template <class CharSet_, template <typename> class StackType_=DefaultStackType>
class XMLPathSelect :public throws_exception
{
public:
        typedef XMLPathSelectAutomaton<CharSet_> ThisXMLPathSelectAutomaton;
        typedef XMLPathSelect<CharSet_,StackType_> ThisXMLPathSelect;

private:
        const ThisXMLPathSelectAutomaton* atm;          //< XML select automaton
        typedef typename ThisXMLPathSelectAutomaton::Mask Mask;
        typedef typename ThisXMLPathSelectAutomaton::Token Token;
        typedef typename ThisXMLPathSelectAutomaton::Hash Hash;
        typedef typename ThisXMLPathSelectAutomaton::State State;
        typedef typename ThisXMLPathSelectAutomaton::Scope Scope;

        struct Context
        {
                XMLScannerBase::ElementType type;       //< element type processed
                const char* key;                        //< string value of element processed
                unsigned int keysize;                   //< size of string value in bytes of element processed
                Scope scope;                            //< active scope
                unsigned int scope_iter;                //< position of currently visited token in the active scope

                Context()                               :type(XMLScannerBase::Content),key(0),keysize(0) {}

                void init( XMLScannerBase::ElementType p_type, const char* p_key, int p_keysize)
                {
                        type = p_type;
                        key = p_key;
                        keysize = p_keysize;
                        scope_iter = scope.range.tokenidx_from;
                }
        };

        StackType_<Scope> scopestk;             //< stack of scopes opened
        StackType_<unsigned int> follows;       //< indices of tokens active in all descendant scopes
        StackType_<int> triggers;               //< triggered elements
        StackType_<Token> tokens;               //< list of waiting tokens
        Context context;                        //< state variables without stacks of the automaton

        void expand( int stateidx)
        {
                while (stateidx!=-1)
                {
                        const State& st = atm->states[ stateidx];
                        context.scope.mask.join( st.core.mask);
                        if (st.core.mask.empty() && st.core.typeidx != 0)
                        {
                                triggers.push_back( st.core.typeidx);
                        }
                        else
                        {
                                if (st.core.follow)
                                {
                                        context.scope.followMask.join( st.core.mask);
                                        follows.push_back( tokens.size());
                                }
                                tokens.push_back( Token( st, stateidx));
                        }
                        stateidx = st.link;
                }
        }

        void initProcessElement( XMLScannerBase::ElementType type, const char* key, int keysize)
        {
                if (context.type == XMLScannerBase::OpenTag)
                {
                        //last step of open scope has to be done after all tokens were visited,
                        //e.g. with the next element initialization
                        context.scope.range.tokenidx_from = context.scope.range.tokenidx_to;
                }
                context.scope.range.tokenidx_to = tokens.size();
                context.scope.range.followidx = follows.size();
                context.init( type, key, keysize);
                if (context.type == XMLScannerBase::OpenTag)
                {
                        // first step of open scope saves the context context on stack
                        scopestk.push_back( context.scope);
                        context.scope.mask = context.scope.followMask;
                        context.scope.mask.match( XMLScannerBase::OpenTag);
                        //... we reset the mask but ensure that this 'OpenTag' is processed for sure
                }
        }

        void closeProcessElement()
        {
                if (context.type == XMLScannerBase::CloseTag || context.type == XMLScannerBase::CloseTagIm)
                {
                        if (!scopestk.empty())
                        {
                                context.scope = scopestk.back();
                                scopestk.pop_back();
                                follows.resize( context.scope.range.followidx);
                                tokens.resize( context.scope.range.tokenidx_to);
                        }
                }
        }

        void produce( unsigned int tokenidx, const State& st)
        {
                const Token& tk = tokens[ tokenidx];
                if (tk.core.cnt_end == -1)
                {
                        expand( st.next);
                }
                else
                {
                        if (tk.core.cnt_end > 0)
                        {
                                if (--tokens[ tokenidx].core.cnt_end == 0)
                                {
                                        tokens[ tokenidx].core.mask.reset();
                                }
                                if (tk.core.cnt_start <= 0)
                                {
                                        expand( st.next);
                                }
                                else
                                {
                                        --tokens[ tokenidx].core.cnt_start;
                                }
                        }
                }
        }

        int match( unsigned int tokenidx)
        {
                int rt = 0;
                if (context.key != 0)
                {
                        if (tokenidx >= context.scope.range.tokenidx_to) return 0;

                        Token* tk = &tokens[ tokenidx];
                        if (tk->core.mask.matches( context.type))
                        {
                                const State& st = atm->states[ tk->stateidx];
                                if (st.key)
                                {
                                        if (st.keysize == context.keysize)
                                        {
                                                unsigned int ii;
                                                for (ii=0; ii<context.keysize && st.key[ii] == context.key[ii]; ii++);
                                                if (ii==context.keysize)
                                                {
                                                        produce( tokenidx, st);
                                                        tk = &tokens[ tokenidx];
                                                }
                                        }
                                }
                                else
                                {
                                        produce( tokenidx, st);
                                        tk = &tokens[ tokenidx];
                                }
                                if (tk->core.typeidx != 0)
                                {
                                        if (tk->core.cnt_end == -1)
                                        {
                                                rt = tk->core.typeidx;
                                        }
                                        else if (tk->core.cnt_end > 0)
                                        {
                                                if (--tk->core.cnt_end == 0)
                                                {
                                                        tk->core.mask.reset();
                                                }
                                                if (tk->core.cnt_start <= 0)
                                                {
                                                        rt = tk->core.typeidx;
                                                }
                                                else
                                                {
                                                        --tk->core.cnt_start;
                                                }
                                        }
                                }
                        }
                        if (tk->core.mask.rejects( context.type))
                        {
                                //The token must not match anymore after encountering a reject item
                                tk->core.mask.reset();
                        }
                }
                return rt;
        }

        int fetch()
        {
                int type = 0;

                if (context.scope.mask.matches( context.type))
                {
                        while (!type)
                        {
                                if (context.scope_iter < context.scope.range.tokenidx_to)
                                {
                                        type = match( context.scope_iter);
                                        ++context.scope_iter;
                                }
                                else
                                {
                                        unsigned int ii = context.scope_iter - context.scope.range.tokenidx_to;
                                        //we match all follows that are not yet been checked in the current scope
                                        if (ii < context.scope.range.followidx && context.scope.range.tokenidx_from > follows[ ii])
                                        {
                                                type = match( follows[ ii]);
                                                ++context.scope_iter;
                                        }
                                        else if (!triggers.empty())
                                        {
                                                type = triggers.back();
                                                triggers.pop_back();
                                        }
                                        else
                                        {
                                                context.key = 0;
                                                context.keysize = 0;
                                                return 0; //end of all candidates
                                        }
                                }
                        }
                }
                else
                {
                        context.key = 0;
                        context.keysize = 0;
                }
                return type;
        }

public:
        template <class Buffer>
        void getTokenTypeMatchingStates( XMLScannerBase::ElementType type, bool withFollows, Buffer& buf) const
        {
                unsigned int ti = context.scope.range.tokenidx_to, te = tokens.size();
                for (; ti<te; ++ti)
                {
                        const Token& tk = tokens[ (std::size_t)ti];
                        if (tk.core.mask.matches( type))
                        {
                                buf.push_back( tokens[ti].stateidx);
                        }
                }
                if (withFollows)
                {
                        ti=0; te = context.scope.range.followidx;
                        for (; ti<te; ++ti)
                        {
                                if (tokens[ follows[ ti]].core.mask.matches( type))
                                {
                                        buf.push_back( tokens[ follows[ ti]].stateidx);
                                }
                        }
                }
        }

public:
        XMLPathSelect( const ThisXMLPathSelectAutomaton* p_atm)
                :atm(p_atm),scopestk(),follows(),triggers(),tokens()
        {
                if (atm->states.size() > 0) expand(0);
        }

        XMLPathSelect( const XMLPathSelect& o)
                :atm(o.atm),scopestk(o.scopestk),follows(o.follows),triggers(o.triggers),tokens(o.tokens){}

        class iterator
        {
        public:
                typedef int value_type;
                typedef std::size_t difference_type;
                typedef int* pointer;
                typedef int& reference;
                typedef std::input_iterator_tag iterator_category;

        private:
                int element;                                    //< currently visited element (type)
                ThisXMLPathSelect* input;                       //< producing XML path selection stream

                iterator& skip() throw(exception,std::bad_alloc)
                {
                        if (input != 0)
                        {
                                element = input->fetch();
                        }
                        else
                        {
                                element = 0;
                        }
                        return *this;
                }

                bool compare( const iterator& iter) const
                {
                        return (element == iter.element);
                }

        public:
                void assign( const iterator& orig)
                {
                        input = orig.input;
                        element = orig.element;
                }

                iterator( const iterator& orig)
                {
                        assign( orig);
                }

                iterator( ThisXMLPathSelect& p_input, XMLScannerBase::ElementType p_type, const char* p_key, int p_keysize)
                                :input( &p_input)
                {
                        input->initProcessElement( p_type, p_key, p_keysize);
                        skip();
                }

                ~iterator()
                {
                        if (input) input->closeProcessElement();
                }

                iterator()
                        :element(0),input(0) {}

                iterator& operator = (const iterator& orig)
                {
                        assign( orig);
                        return *this;
                }

                int operator*() const
                {
                        return element;
                }

                const int* operator->() const
                {
                        return &element;
                }

                iterator& operator++()                          {return skip();}

                iterator operator++(int)                        {iterator tmp(*this); skip(); return tmp;}

                bool operator==( const iterator& iter) const    {return compare( iter);}

                bool operator!=( const iterator& iter) const    {return !compare( iter);}
        };

        iterator push( XMLScannerBase::ElementType type, const char* key, int keysize)
        {
                return iterator( *this, type, key, keysize);
        }

        iterator push( XMLScannerBase::ElementType type, const std::string& key)
        {
                return iterator( *this, type, key.c_str(), key.size());
        }

        iterator end()
        {
                return iterator();
        }
};

}//namespace
#endif