multi_pass.hpp

C++的一个好库。。。现在很流行

/*=============================================================================
    Copyright (c) 2001, Daniel C. Nuffer
    http://spirit.sourceforge.net/

    Use, modification and distribution is subject to the Boost Software
    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
#ifndef BOOST_SPIRIT_ITERATOR_MULTI_PASS_HPP
#define BOOST_SPIRIT_ITERATOR_MULTI_PASS_HPP

#include <boost/config.hpp>
#include <boost/throw_exception.hpp>
#include <deque>
#include <iterator>
#include <iostream>
#include <algorithm>    // for std::swap
#include <exception>    // for std::exception
#include <boost/limits.hpp>
#include <boost/iterator.hpp>

#include <boost/spirit/core/assert.hpp> // for BOOST_SPIRIT_ASSERT
#include <boost/spirit/iterator/fixed_size_queue.hpp>
#include <boost/detail/iterator.hpp> // for boost::detail::iterator_traits

namespace boost { namespace spirit {

namespace impl {
    template <typename T>
    inline void mp_swap(T& t1, T& t2);
}

namespace multi_pass_policies
{

///////////////////////////////////////////////////////////////////////////////
// class ref_counted
// Implementation of an OwnershipPolicy used by multi_pass.
//
// Implementation modified from RefCounted class from the Loki library by
// Andrei Alexandrescu
///////////////////////////////////////////////////////////////////////////////
class ref_counted
{
    protected:
        ref_counted()
            : count(new std::size_t(1))
        {}

        ref_counted(ref_counted const& x)
            : count(x.count)
        {}

        // clone is called when a copy of the iterator is made, so increment
        // the ref-count.
        void clone()
        {
            ++*count;
        }

        // called when a copy is deleted.  Decrement the ref-count.  Return
        // value of true indicates that the last copy has been released.
        bool release()
        {
            if (!--*count)
            {
                delete count;
                count = 0;
                return true;
            }
            return false;
        }

        void swap(ref_counted& x)
        {
            impl::mp_swap(count, x.count);
        }

    public:
        // returns true if there is only one iterator in existence.
        // std_deque StoragePolicy will free it's buffered data if this
        // returns true.
        bool unique() const
        {
            return *count == 1;
        }

    private:
        std::size_t* count;
};

///////////////////////////////////////////////////////////////////////////////
// class first_owner
// Implementation of an OwnershipPolicy used by multi_pass
// This ownership policy dictates that the first iterator created will
// determine the lifespan of the shared components.  This works well for
// spirit, since no dynamic allocation of iterators is done, and all copies
// are make on the stack.
//
// There is a caveat about using this policy together with the std_deque
// StoragePolicy. Since first_owner always returns false from unique(),
// std_deque will only release the queued data if clear_queue() is called.
///////////////////////////////////////////////////////////////////////////////
class first_owner
{
    protected:
        first_owner()
            : first(true)
        {}

        first_owner(first_owner const&)
            : first(false)
        {}

        void clone()
        {
        }

        // return true to indicate deletion of resources
        bool release()
        {
            return first;
        }

        void swap(first_owner&)
        {
            // if we're the first, we still remain the first, even if assigned
            // to, so don't swap first_.  swap is only called from operator=
        }

    public:
        bool unique() const
        {
            return false; // no way to know, so always return false
        }

    private:
        bool first;
};

///////////////////////////////////////////////////////////////////////////////
// class illegal_backtracking
// thrown by buf_id_check CheckingPolicy if an instance of an iterator is
// used after another one has invalidated the queue
///////////////////////////////////////////////////////////////////////////////
class illegal_backtracking : public std::exception
{
public:

    illegal_backtracking() throw() {}
    ~illegal_backtracking() throw() {}

    virtual const char*
    what() const throw()
    { return "boost::spirit::illegal_backtracking"; }
};

///////////////////////////////////////////////////////////////////////////////
// class buf_id_check
// Implementation of the CheckingPolicy used by multi_pass
// This policy is most effective when used together with the std_deque
// StoragePolicy.
// If used with the fixed_size_queue StoragePolicy, it will not detect
// iterator derefereces that are out of the range of the queue.
///////////////////////////////////////////////////////////////////////////////
class buf_id_check
{
    protected:
        buf_id_check()
            : shared_buf_id(new unsigned long(0))
            , buf_id(0)
        {}

        buf_id_check(buf_id_check const& x)
            : shared_buf_id(x.shared_buf_id)
            , buf_id(x.buf_id)
        {}

        // will be called from the destructor of the last iterator.
        void destroy()
        {
            delete shared_buf_id;
            shared_buf_id = 0;
        }

        void swap(buf_id_check& x)
        {
            impl::mp_swap(shared_buf_id, x.shared_buf_id);
            impl::mp_swap(buf_id, x.buf_id);
        }

        // called to verify that everything is okay.
        void check() const
        {
            if (buf_id != *shared_buf_id)
            {
                boost::throw_exception(illegal_backtracking());
            }
        }

        // called from multi_pass::clear_queue, so we can increment the count
        void clear_queue()
        {
            ++*shared_buf_id;
            ++buf_id;
        }

    private:
        unsigned long* shared_buf_id;
        unsigned long buf_id;
};

///////////////////////////////////////////////////////////////////////////////
// class no_check
// Implementation of the CheckingPolicy used by multi_pass
// It does not do anything :-)
///////////////////////////////////////////////////////////////////////////////
class no_check
{
    protected:
        no_check() {}
        no_check(no_check const&) {}
        void destroy() {}
        void swap(no_check&) {}
        void check() const {}
        void clear_queue() {}
};

///////////////////////////////////////////////////////////////////////////////
// class std_deque
// Implementation of the StoragePolicy used by multi_pass
// This stores all data in a std::deque, and keeps an offset to the current
// position. It stores all the data unless there is only one
// iterator using the queue.
// Note: a position is used instead of an iterator, because a push_back on
// a deque can invalidate any iterators.
///////////////////////////////////////////////////////////////////////////////
class std_deque
{
    public:

template <typename ValueT>
class inner
{
    private:

        typedef std::deque<ValueT> queue_type;
        queue_type* queuedElements;
        mutable typename queue_type::size_type queuePosition;

    protected:
        inner()
            : queuedElements(new queue_type)
            , queuePosition(0)
        {}

        inner(inner const& x)
            : queuedElements(x.queuedElements)
            , queuePosition(x.queuePosition)
        {}

        // will be called from the destructor of the last iterator.
        void destroy()
        {
            BOOST_SPIRIT_ASSERT(NULL != queuedElements);
            delete queuedElements;
            queuedElements = 0;
        }

        void swap(inner& x)
        {
            impl::mp_swap(queuedElements, x.queuedElements);
            impl::mp_swap(queuePosition, x.queuePosition);
        }

        // This is called when the iterator is dereferenced.  It's a template
        // method so we can recover the type of the multi_pass iterator
        // and call unique and access the m_input data member.
        template <typename MultiPassT>
        static typename MultiPassT::reference dereference(MultiPassT const& mp)
        {
            if (mp.queuePosition == mp.queuedElements->size())
            {
                // check if this is the only iterator
                if (mp.unique())
                {
                    // free up the memory used by the queue.
                    if (mp.queuedElements->size() > 0)
                    {
                        mp.queuedElements->clear();
                        mp.queuePosition = 0;
                    }
                }
                return mp.get_input();
            }
            else
            {
                return (*mp.queuedElements)[mp.queuePosition];
            }
        }

        // This is called when the iterator is incremented.  It's a template
        // method so we can recover the type of the multi_pass iterator
        // and call unique and access the m_input data member.
        template <typename MultiPassT>
        static void increment(MultiPassT& mp)
        {
            if (mp.queuePosition == mp.queuedElements->size())
            {
                // check if this is the only iterator
                if (mp.unique())
                {
                    // free up the memory used by the queue.
                    if (mp.queuedElements->size() > 0)
                    {
                        mp.queuedElements->clear();
                        mp.queuePosition = 0;
                    }
                }
                else
                {
                    mp.queuedElements->push_back(mp.get_input());
                    ++mp.queuePosition;
                }
                mp.advance_input();
            }
            else
            {
                ++mp.queuePosition;
            }

        }

        // called to forcibly clear the queue
        void clear_queue()
        {
            queuedElements->clear();
            queuePosition = 0;
        }

        // called to determine whether the iterator is an eof iterator
        template <typename MultiPassT>
        static bool is_eof(MultiPassT const& mp)
        {
            return mp.queuePosition == mp.queuedElements->size() &&
                mp.input_at_eof();
        }

        // called by operator==
        bool equal_to(inner const& x) const
        {
            return queuePosition == x.queuePosition;
        }

        // called by operator<
        bool less_than(inner const& x) const
        {
            return queuePosition < x.queuePosition;
        }
}; // class inner

}; // class std_deque


///////////////////////////////////////////////////////////////////////////////
// class fixed_size_queue
// Implementation of the StoragePolicy used by multi_pass
// fixed_size_queue keeps a circular buffer (implemented by
// boost::spirit::fixed_size_queue class) that is size N+1 and stores N elements.
// It is up to the user to ensure that there is enough look ahead for their
// grammar.  Currently there is no way to tell if an iterator is pointing
// to forgotten data.  The leading iterator will put an item in the queue
// and remove one when it is incremented.  No dynamic allocation is done,
// except on creation of the queue (fixed_size_queue constructor).
///////////////////////////////////////////////////////////////////////////////
template < std::size_t N>
class fixed_size_queue
{
    public:

template <typename ValueT>
class inner
{
    private:

        typedef boost::spirit::fixed_size_queue<ValueT, N> queue_type;
        queue_type * queuedElements;
        mutable typename queue_type::iterator queuePosition;

    protected:
        inner()
            : queuedElements(new queue_type)
            , queuePosition(queuedElements->begin())
        {}

        inner(inner const& x)
            : queuedElements(x.queuedElements)
            , queuePosition(x.queuePosition)
        {}

        // will be called from the destructor of the last iterator.
        void destroy()
        {
            BOOST_SPIRIT_ASSERT(NULL != queuedElements);
            delete queuedElements;
            queuedElements = 0;
        }

        void swap(inner& x)
        {
            impl::mp_swap(queuedElements, x.queuedElements);
            impl::mp_swap(queuePosition, x.queuePosition);
        }

        // This is called when the iterator is dereferenced.  It's a template
        // method so we can recover the type of the multi_pass iterator
        // and access the m_input data member.
        template <typename MultiPassT>
        static typename MultiPassT::reference dereference(MultiPassT const& mp)
        {
            if (mp.queuePosition == mp.queuedElements->end())
            {
                return mp.get_input();
            }
            else
            {
                return *mp.queuePosition;
            }
        }

        // This is called when the iterator is incremented.  It's a template
        // method so we can recover the type of the multi_pass iterator
        // and access the m_input data member.
        template <typename MultiPassT>
        static void increment(MultiPassT& mp)
        {
            if (mp.queuePosition == mp.queuedElements->end())