xtl_primary.h

Go to the documentation of this file.

// Common Text Transformation Library
// Copyright (C) 1997-2006 by Igor Kholodov. 
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the
// Free Software Foundation, Inc.,
// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
//
// mailto:cttl@users.sourceforge.net
// http://sourceforge.net/projects/cttl/

// xtl_primary.h

#ifndef _CTTL_XTL_PRIMARY_H_INCLUDED_
#define _CTTL_XTL_PRIMARY_H_INCLUDED_

#include <set>

namespace cttl_impl {

template< typename DerivedT >
struct xtl_primary {

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // check white space
        size_t saved_first_offset = edge_.space_policy().match( edge_ );

        if ( edge_.length() <= 0 ) {
            // restore original position
            edge_.first.offset( saved_first_offset );
            CTTL_TRACE_TEXT_RESULT( false, 'L', "empty universe" );
            return UniverseT::string_T::npos;
        }

        // edge_.first is now guaranteed to be outside white space

        size_t match_offset = static_cast< DerivedT* >( this )->internal_match( edge_ );

        if ( match_offset == UniverseT::string_T::npos ) {
            // match failed:
            // restore original position
            edge_.first.offset( saved_first_offset );
            return UniverseT::string_T::npos;
        }

        if ( edge_.length() < 0 ) {
            // although match suceeded, it is beyond universe bounds.
            // restore original position
            edge_.first.offset( saved_first_offset );
            CTTL_TRACE_TEXT_RESULT( false, 'L', "lexeme match out-of-universe bounds" );
            return UniverseT::string_T::npos;
        }

        // here:
        //  match_offset is starting position (upper boundary) of the matched symbol;
        //  edge_.first.offset() is symbol ending position (lower boundary);
        //  primary_length( match_offset, edge_ ) is symbol length.

        //  if primary_length() is greater than zero, then edge_.first.offset()
        //  minus 1 is points to the last character of the matched symbol.

        // check lower boundary of the lexeme against client regions:
        if ( primary_length( match_offset, edge_.first.offset() ) ) {
            // offset of the previous character
            size_t offset_minus_one = edge_.first.offset() - 1;
            if ( offset_minus_one != edge_.space_policy().lower_bound( offset_minus_one, edge_.second.offset() ) ) {
                // No additional match attemts needed, because
                // symbol is atomic object, it cannot be split by client regions.
                // Upper bound of the symbol is inside client region.
                // Restore original position and fail:
                edge_.first.offset( saved_first_offset );
                CTTL_TRACE_TEXT_RESULT( false, 'L', "lexeme match inside void space" );
                return UniverseT::string_T::npos;
            }
        }

        // success
        return match_offset;
    }

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        size_t saved_first_offset = edge_.first.offset();

replay_find:
        if ( edge_.length() <= 0 ) {
            // proposed universe is invalid
            // restore original position
            edge_.first.offset( saved_first_offset );
            CTTL_TRACE_TEXT_RESULT( false, 'L', "lexeme find: invalid universe" );
            return UniverseT::string_T::npos;
        }

        size_t offset_before_replay = edge_.first.offset();
        size_t match_offset = static_cast< DerivedT* >( this )->internal_find( edge_ );

        if ( match_offset == UniverseT::string_T::npos ) {
            // find failed:
            // restore original position
            edge_.first.offset( saved_first_offset );
            return UniverseT::string_T::npos;
        }

        // here:
        //  match_offset is starting position (upper boundary) of the matched symbol;
        //  edge_.first.offset() is symbol ending position (lower boundary);
        //  primary_length( match_offset, edge_ ) is symbol length.

        //  if primary_length() is greater than zero, then edge_.first.offset()
        //  minus 1 is points to the last character of the matched symbol.

        if ( edge_.length() < 0 ) {
            // find suceeded beyond lower boundary of the universe:
            // restore original position
            edge_.first.offset( saved_first_offset );
            CTTL_TRACE_TEXT_RESULT( false, 'L', "lexeme find: out-of-universe bounds" );
            return UniverseT::string_T::npos;
        }

        // Check if symbol boundaries are outside
        // existing client regions:

        if ( edge_.space_policy().lower_bound( match_offset, edge_ ) ) {
            // Upper boundary is inside of a client region.
            // Replay the search, if edge_.first.offset()
            // has made actual progress since last time:
            if ( offset_before_replay < edge_.first.offset() )
                goto replay_find;

            edge_.first.offset( saved_first_offset );
            CTTL_TRACE_TEXT_RESULT( false, 'L', "lexeme find: lower bound inside void region" );
            return UniverseT::string_T::npos;
        }

        if ( primary_length( match_offset, edge_.first.offset() )
            &&
            edge_.space_policy().lower_bound( edge_.first.offset() - 1, edge_ ) )
        {
            // Lower boundary is inside a client region.
            // Replay the search, if edge_.first.offset()
            // has made actual progress since last time:
            if ( offset_before_replay < edge_.first.offset() )
                goto replay_find;

            edge_.first.offset( saved_first_offset );
            CTTL_TRACE_TEXT_RESULT( false, 'L', "lexeme find: upper bound inside void region" );
            return UniverseT::string_T::npos;
        }

        // success
        return match_offset;
    }

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        return find( edge_ );
    }

protected:
    int primary_length( size_t upper_offset_, size_t lower_offset_ ) const
    {
        return lower_offset_ - upper_offset_;
    }

};  // xtl_primary

template< bool accept_emty_universe = false >
class xtl_bool {

private:
    bool m_value;

public:
    // compile-time

    xtl_bool( bool value_ )
    : m_value( value_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        if ( !accept_emty_universe && m_value && !edge_.length() ) {
            CTTL_TRACE_TEXT_RESULT( false, char( '0' + int( m_value ) ), "epsilon match: empty universe" );
            return UniverseT::string_T::npos;
        }

        return internal_match( edge_ );
    }

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        return internal_match( edge_ );
    }

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        return internal_match( edge_ );
    }

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typedef typename UniverseT::char_T char_T;
        // edge state is ready;
        // set correct offset of this lexeme:
        if ( m_value ) {
            CTTL_TRACE_RESULT( true, char( '0' + int( m_value ) ) );
            return edge_.first.offset();
        } else {
            CTTL_TRACE_RESULT( false, char( '0' + int( m_value ) ) );
            return UniverseT::string_T::npos;
        }
    }

};  // class xtl_bool


template< typename StringT >
class xtl_keyword {

private:
    std::set< StringT > const& m_keywords;

public:
    // compile-time

    xtl_keyword( std::set< StringT > const& keywords_ )
    : m_keywords( keywords_ )
    {
    }

    void operator=( xtl_keyword< StringT > const& ) const
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT const& edge_ ) const
    {
        // edge state is ready;
        // return correct offset of this lexeme:
        if ( m_keywords.find( edge_.text() ) != m_keywords.end() ) {
            CTTL_TRACE_RESULT( true, 'S' );
            return edge_.first.offset();
        }

        CTTL_TRACE_RESULT( false, 'S' );
        return UniverseT::string_T::npos;
    }

};  // xtl_keyword


class xtl_char_symbol : public xtl_primary< xtl_char_symbol > {

public:

    // run-time

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        return xtl_primary< xtl_char_symbol >::match( edge_ );
    }

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        return xtl_primary< xtl_char_symbol >::match( edge_ );
    }

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        // successful match
        // set match starting position
        size_t match_offset = edge_.first.offset();
        // set match ending position
        edge_.first.offset( match_offset + 1 );
        CTTL_TRACE_TEXT_RESULT( true, edge_.first[ -1 ], "symbol" );
        return match_offset;
    }

};  // xtl_char_symbol


template< typename CharT >
class xtl_char : public xtl_primary< xtl_char< CharT > > {

private:
    CharT m_char;

public:
    // compile-time

    xtl_char( CharT char_ )
    : m_char( char_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        if ( edge_.parent().text()[ edge_.first.offset() ] == m_char ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();
            // set match ending position
            edge_.first.offset( match_offset + 1 );
            CTTL_TRACE_TEXT_RESULT( true, m_char, "char" );
            return match_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, m_char, "char" );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        size_t new_offset = edge_.parent().text().find( m_char, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // set find ending position
            edge_.first.offset( new_offset + 1 );
            CTTL_TRACE_TEXT_RESULT( true, m_char, "char" );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, m_char, "char" );
        return UniverseT::string_T::npos;
    }
};  // xtl_char


template< typename CharT >
class xtl_char_begin : public xtl_primary< xtl_char_begin< CharT > > {

private:
    CharT m_char;

public:
    // compile-time

    xtl_char_begin( CharT char_ )
    : m_char( char_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        if ( edge_.parent().text()[ edge_.first.offset() ] == m_char ) {
            // successful match
            CTTL_TRACE_TEXT_RESULT( true, m_char, "begin( char )" );
            // set match starting position
            return edge_.first.offset();
        }

        CTTL_TRACE_TEXT_RESULT( false, m_char, "begin( char )" );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        size_t new_offset = edge_.parent().text().find( m_char, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // set find ending position
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, m_char, "begin( char )" );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, m_char, "begin( char )" );
        return UniverseT::string_T::npos;
    }

};  // xtl_char_begin


template< typename CharT >
class xtl_char_end : public xtl_primary< xtl_char_end< CharT > > {

private:
    CharT m_char;

public:
    // compile-time

    xtl_char_end( CharT char_ )
    : m_char( char_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        if ( edge_.parent().text()[ edge_.first.offset() ] == m_char ) {
            // match starting and ending position are the same
            edge_.first.offset( edge_.first.offset() + 1 );
            CTTL_TRACE_TEXT_RESULT( true, m_char, "end( char )" );
            return edge_.first.offset();
        }

        CTTL_TRACE_TEXT_RESULT( false, m_char, "end( char )" );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        size_t new_offset = edge_.parent().text().find( m_char, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // set find ending position
            edge_.first.offset( ++new_offset );
            CTTL_TRACE_TEXT_RESULT( true, m_char, "end( char )" );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, m_char, "end( char )" );
        return UniverseT::string_T::npos;
    }
};  // xtl_char_end



class xtl_iswhat_begin : public xtl_primary< xtl_iswhat_begin > {

private:
    iswhat_T m_iswhat;

public:
    // compile-time

    xtl_iswhat_begin( iswhat_T iswhat_ )
    : m_iswhat( iswhat_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT const& edge_ )
    {
        if ( m_iswhat( edge_.parent().text()[ edge_.first.offset() ] ) ) {
            // successful match: ending position is current:
            CTTL_TRACE_RESULT( true, '<' );
            return edge_.first.offset();
        }
        CTTL_TRACE_RESULT( false, '<' );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();

        // find starting position
        it = std::find_if( it, str.end(), m_iswhat );
        if ( it == str.end() ) {
            CTTL_TRACE_RESULT( false, '<' );
            return UniverseT::string_T::npos;
        }

        size_t new_offset = std::distance( str.begin(), it );
        edge_.first.offset( new_offset );
        CTTL_TRACE_RESULT( true, '<' );
        return new_offset;
    }

};  // xtl_iswhat_begin


class xtl_iswhat_first : public xtl_primary< xtl_iswhat_first > {

private:
    iswhat_T m_iswhat;

public:
    // compile-time

    xtl_iswhat_first( iswhat_T iswhat_ )
    : m_iswhat( iswhat_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        if ( m_iswhat( edge_.parent().text()[ edge_.first.offset() ] ) ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();
            // ending position:
            // at least one character in this entity is present
            edge_.first.offset( edge_.first.offset() + 1 );
            CTTL_TRACE_RESULT( true, 'F' );
            return match_offset;
        }
        CTTL_TRACE_RESULT( false, 'F' );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();

        // find starting position
        it = std::find_if( it, str.end(), m_iswhat );
        if ( it == str.end() ) {
            CTTL_TRACE_RESULT( false, 'F' );
            return UniverseT::string_T::npos;
        }

        size_t new_offset = std::distance( str.begin(), it );
        // set find ending position:
        // at least one character in this entity is present
        edge_.first.offset( new_offset + 1 );
        CTTL_TRACE_RESULT( true, 'F' );
        return new_offset;
    }

};  // xtl_iswhat_first


class xtl_iswhat_end : public xtl_primary< xtl_iswhat_end > {

private:
    iswhat_T m_iswhat;

public:
    // compile-time

    xtl_iswhat_end( iswhat_T iswhat_ )
    : m_iswhat( iswhat_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        size_t match_offset = xtl_primary< xtl_iswhat_end >::match( edge_ );

        if ( match_offset != UniverseT::string_T::npos ) {
            return edge_.first.offset();
        }
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        if ( m_iswhat( edge_.parent().text()[ edge_.first.offset() ] ) ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();

            // find ending position
            typename UniverseT::string_T const& str = edge_.parent().text();
            typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();
            it = std::find_if( it, str.end(), std::not1( std::ptr_fun( m_iswhat ) ) );
            // set ending position
            if ( it != str.end() )
                edge_.first.offset( std::distance( str.begin(), it ) );
            else
                edge_.first.offset( str.length() );

            CTTL_TRACE_RESULT( true, '>' );
            return match_offset;

        } else if ( edge_.first.offset() ) {
            // check if we are at the entity-end position:
            // offset of the previous character
            size_t offset_minus_one = edge_.first.offset() - 1;
            if ( offset_minus_one != edge_.space_policy().lower_bound( offset_minus_one, edge_.second.offset() ) ) {
                // offset_minus_one is in the void space
                CTTL_TRACE_RESULT( false, '>' );
                return UniverseT::string_T::npos;
            }

            if ( m_iswhat( edge_.parent().text()[ offset_minus_one ] ) ) {
                // successful match
                CTTL_TRACE_RESULT( true, '>' );
                return edge_.first.offset();
            }
        }
        CTTL_TRACE_RESULT( false, '>' );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();

        // find starting position
        it = std::find_if( it, str.end(), m_iswhat );
        if ( it == str.end() ) {
            CTTL_TRACE_RESULT( false, '>' );
            return UniverseT::string_T::npos;
        }

        // find ending position
        size_t new_offset = UniverseT::string_T::npos;
        it = std::find_if( it, str.end(), std::not1( std::ptr_fun( m_iswhat ) ) );
        if ( it != str.end() )
            new_offset = std::distance( str.begin(), it );
        else
            new_offset = str.length();

        // set find ending position
        edge_.first.offset( new_offset );
        CTTL_TRACE_RESULT( true, '>' );
        return new_offset;
    }

};  // xtl_iswhat_end


class xtl_iswhat_entity : public xtl_primary< xtl_iswhat_entity > {

private:
    iswhat_T m_iswhat;

public:
    // compile-time

    xtl_iswhat_entity( iswhat_T iswhat_ )
    : m_iswhat( iswhat_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        if ( m_iswhat( edge_.parent().text()[ edge_.first.offset() ] ) ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();

            // find ending position
            typename UniverseT::string_T const& str = edge_.parent().text();
            typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();
            it = std::find_if( it, str.end(), std::not1( std::ptr_fun( m_iswhat ) ) );
            // set ending position
            if ( it != str.end() )
                edge_.first.offset( std::distance( str.begin(), it ) );
            else
                edge_.first.offset( str.length() );

            CTTL_TRACE_RESULT( true, '$' );
            return match_offset;
        }
        CTTL_TRACE_RESULT( false, '$' );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();

        // find starting position
        it = std::find_if( it, str.end(), m_iswhat );
        if ( it == str.end() ) {
            CTTL_TRACE_RESULT( false, '$' );
            return UniverseT::string_T::npos;
        }

        size_t new_offset = std::distance( str.begin(), it );
        // set find starting position
        size_t match_offset = new_offset;

        // find ending position
        it = std::find_if( it, str.end(), std::not1( std::ptr_fun( m_iswhat ) ) );
        if ( it != str.end() )
            new_offset = std::distance( str.begin(), it );
        else
            new_offset = str.length();

        // set find ending position
        edge_.first.offset( new_offset );
        CTTL_TRACE_RESULT( true, '$' );
        return match_offset;
    }

};  // xtl_iswhat_entity


class xtl_iswwhat_begin : public xtl_primary< xtl_iswwhat_begin > {

private:
    iswwhat_T m_iswwhat;

public:
    // compile-time

    xtl_iswwhat_begin( iswwhat_T iswwhat_ )
    : m_iswwhat( iswwhat_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT const& edge_ )
    {
        if ( m_iswwhat( edge_.parent().text()[ edge_.first.offset() ] ) ) {
            // successful match: ending position is current:
            CTTL_TRACE_RESULT( true, '<' );
            return edge_.first.offset();
        }
        CTTL_TRACE_RESULT( false, '<' );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();

        // find starting position
        it = std::find_if( it, str.end(), m_iswwhat );
        if ( it == str.end() ) {
            CTTL_TRACE_RESULT( false, '<' );
            return UniverseT::string_T::npos;
        }

        size_t new_offset = std::distance( str.begin(), it );
        // ending position is the same
        edge_.first.offset( new_offset );
        CTTL_TRACE_RESULT( true, '<' );
        return new_offset;
    }

};  // xtl_iswwhat_begin


class xtl_iswwhat_first : public xtl_primary< xtl_iswwhat_first > {

private:
    iswwhat_T m_iswwhat;

public:
    // compile-time

    xtl_iswwhat_first( iswwhat_T iswwhat_ )
    : m_iswwhat( iswwhat_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        if ( m_iswwhat( edge_.parent().text()[ edge_.first.offset() ] ) ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();
            // ending position: at least one character in this entity is present
            edge_.first.offset( edge_.first.offset() + 1 );
            CTTL_TRACE_RESULT( true, 'F' );
            return match_offset;
        }
        CTTL_TRACE_RESULT( false, 'F' );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();

        // find starting position
        it = std::find_if( it, str.end(), m_iswwhat );
        if ( it == str.end() ) {
            CTTL_TRACE_RESULT( false, 'F' );
            return UniverseT::string_T::npos;
        }

        size_t new_offset = std::distance( str.begin(), it );
        // set find ending position: at least one character
        // in this entity is present
        edge_.first.offset( new_offset + 1 );
        CTTL_TRACE_RESULT( true, 'F' );
        return new_offset;
    }

};  // xtl_iswwhat_first


class xtl_iswwhat_end : public xtl_primary< xtl_iswwhat_end > {

private:
    iswwhat_T m_iswwhat;

public:
    // compile-time

    xtl_iswwhat_end( iswwhat_T iswwhat_ )
    : m_iswwhat( iswwhat_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        size_t match_offset = xtl_primary< xtl_iswwhat_end >::match( edge_ );

        if ( match_offset != UniverseT::string_T::npos ) {
            return edge_.first.offset();
        }
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        if ( m_iswwhat( edge_.parent().text()[ edge_.first.offset() ] ) ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();

            // find ending position
            typename UniverseT::string_T const& str = edge_.parent().text();
            typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();
            it = std::find_if( it, str.end(), std::not1( std::ptr_fun( m_iswwhat ) ) );
            // set ending position
            if ( it != str.end() )
                edge_.first.offset( std::distance( str.begin(), it ) );
            else
                edge_.first.offset( str.length() );

            CTTL_TRACE_RESULT( true, '>' );
            return match_offset;

        } else if ( edge_.first.offset() ) {
            // check if we are at the entity-end position:
            // offset of the previous character
            size_t offset_minus_one = edge_.first.offset() - 1;
            if ( offset_minus_one != edge_.space_policy().lower_bound( offset_minus_one, edge_.second.offset() ) ) {
                // offset_minus_one is in the void space
                CTTL_TRACE_RESULT( false, '>' );
                return UniverseT::string_T::npos;
            }

            if ( m_iswwhat( edge_.parent().text()[ offset_minus_one ] ) ) {
                // successful match
                CTTL_TRACE_RESULT( true, '>' );
                return edge_.first.offset();
            }
        }
        CTTL_TRACE_RESULT( false, '>' );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();

        // find starting position
        it = std::find_if( it, str.end(), m_iswwhat );
        if ( it == str.end() ) {
            CTTL_TRACE_RESULT( false, '>' );
            return UniverseT::string_T::npos;
        }

        // find ending position
        size_t new_offset = UniverseT::string_T::npos;
        it = std::find_if( it, str.end(), std::not1( std::ptr_fun( m_iswwhat ) ) );
        if ( it != str.end() )
            new_offset = std::distance( str.begin(), it );
        else
            new_offset = str.length();

        // set find ending position
        edge_.first.offset( new_offset );
        // note: LHS is always checked for void space.
        // because the length of this lexeme is zero,
        // test for RHS void space is never
        // attempted, which is the desired behavior
        CTTL_TRACE_RESULT( true, '>' );
        return new_offset;
    }

};  // xtl_iswwhat_end


class xtl_iswwhat_entity : public xtl_primary< xtl_iswwhat_entity > {

private:
    iswwhat_T m_iswwhat;

public:
    // compile-time

    xtl_iswwhat_entity( iswwhat_T iswwhat_ )
    : m_iswwhat( iswwhat_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        if ( m_iswwhat( edge_.parent().text()[ edge_.first.offset() ] ) ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();

            // find ending position
            typename UniverseT::string_T const& str = edge_.parent().text();
            typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();
            it = std::find_if( it, str.end(), std::not1( std::ptr_fun( m_iswwhat ) ) );
            // set ending position
            if ( it != str.end() )
                edge_.first.offset( std::distance( str.begin(), it ) );
            else
                edge_.first.offset( str.length() );

            CTTL_TRACE_RESULT( true, '$' );
            return match_offset;
        }
        CTTL_TRACE_RESULT( false, '$' );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        typename UniverseT::string_T::const_iterator it = str.begin() + edge_.first.offset();

        // find starting position
        it = std::find_if( it, str.end(), m_iswwhat );
        if ( it == str.end() ) {
            CTTL_TRACE_RESULT( false, '$' );
            return UniverseT::string_T::npos;
        }

        size_t new_offset = std::distance( str.begin(), it );
        // set find starting position
        size_t match_offset = new_offset;

        // find ending position
        it = std::find_if( it, str.end(), std::not1( std::ptr_fun( m_iswwhat ) ) );
        if ( it != str.end() )
            new_offset = std::distance( str.begin(), it );
        else
            new_offset = str.length();

        // set find ending position
        edge_.first.offset( new_offset );
        CTTL_TRACE_RESULT( true, '$' );
        return match_offset;
    }

};  // xtl_iswwhat_entity


template< typename StringT >
class xtl_text_begin : public xtl_primary< xtl_text_begin< StringT > > {

private:
    StringT m_any_text;

public:
    // compile-time

    xtl_text_begin( StringT const& any_text_ )
        : m_any_text( any_text_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( m_any_text.find( str[ edge_.first.offset() ] ) != UniverseT::string_T::npos ) {
            // successful match
            // ending position is the same
            CTTL_TRACE_TEXT_RESULT( true, '<', m_any_text.c_str() );
            return edge_.first.offset();
        }

        CTTL_TRACE_TEXT_RESULT( false, '<', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        size_t new_offset = str.find_first_of( m_any_text, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // ending position is the same
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, '<', m_any_text.c_str() );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, '<', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_begin


template< typename StringT >
class xtl_text_ref_begin : public xtl_primary< xtl_text_ref_begin< StringT > > {

private:
    StringT const& m_any_text;

public:
    // compile-time

    xtl_text_ref_begin( StringT const* str_ptr_ )
        : m_any_text( *str_ptr_ )
    {
    }

    void operator=( xtl_text_ref_begin< StringT > const& ) const
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( m_any_text.find( str[ edge_.first.offset() ] ) != UniverseT::string_T::npos ) {
            // successful match
            // ending position is current
            CTTL_TRACE_TEXT_RESULT( true, '<', m_any_text.c_str() );
            return edge_.first.offset();
        }

        CTTL_TRACE_TEXT_RESULT( false, '<', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        size_t new_offset = str.find_first_of( m_any_text, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // ending position is the same
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, '<', m_any_text.c_str() );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, '<', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_ref_begin


template< typename StringT >
class xtl_text_end : public xtl_primary< xtl_text_end< StringT > > {

private:
    StringT m_any_text;

public:
    // compile-time

    xtl_text_end( StringT const& any_text_ )
        : m_any_text( any_text_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        size_t match_offset = xtl_primary< xtl_text_end >::match( edge_ );
        if ( match_offset != UniverseT::string_T::npos ) {
            return edge_.first.offset();
        }
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( m_any_text.find( str[ edge_.first.offset() ] ) != UniverseT::string_T::npos ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();

            // find ending position
            size_t new_offset = str.find_first_not_of( m_any_text, edge_.first.offset() );
            if ( new_offset == UniverseT::string_T::npos )
                new_offset = str.length();

            // set match ending position
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, '>', m_any_text.c_str() );
            return match_offset;

        } else if ( edge_.first.offset() ) {
            // check if we are at the entity-end position:
            // offset of the previous character
            size_t offset_minus_one = edge_.first.offset() - 1;
            if ( offset_minus_one != edge_.space_policy().lower_bound( offset_minus_one, edge_.second.offset() ) ) {
                // offset_minus_one is in the void space
                CTTL_TRACE_TEXT_RESULT( false, '>', m_any_text.c_str() );
                return UniverseT::string_T::npos;
            }

            if ( m_any_text.find( str[ offset_minus_one ] ) != UniverseT::string_T::npos ) {
                // successful match
                CTTL_TRACE_TEXT_RESULT( true, '>', m_any_text.c_str() );
                return edge_.first.offset();
            }
        }

        CTTL_TRACE_TEXT_RESULT( false, '>', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        size_t new_offset = str.find_first_of( m_any_text, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // find ending position
            new_offset = str.find_first_not_of( m_any_text, new_offset );
            if ( new_offset == UniverseT::string_T::npos )
                new_offset = str.length();

            // set ending position
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, '>', m_any_text.c_str() );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, '>', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_end


template< typename StringT >
class xtl_text_ref_end : public xtl_primary< xtl_text_ref_end< StringT > > {

private:
    StringT const& m_any_text;

public:
    // compile-time

    xtl_text_ref_end( StringT const* str_ptr_ )
        : m_any_text( *str_ptr_ )
    {
    }

    void operator=( xtl_text_ref_end< StringT > const& ) const
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        size_t match_offset = xtl_primary< xtl_text_ref_end >::match( edge_ );
        if ( match_offset != UniverseT::string_T::npos ) {
            return edge_.first.offset();
        }
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( m_any_text.find( str[ edge_.first.offset() ] ) != UniverseT::string_T::npos ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();

            // find ending position
            size_t new_offset = str.find_first_not_of( m_any_text, edge_.first.offset() );
            if ( new_offset == UniverseT::string_T::npos )
                new_offset = str.length();

            // set match ending position
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, '>', m_any_text.c_str() );
            return match_offset;

        } else if ( edge_.first.offset() ) {
            // check if we are at the entity end position:
            // offset of the previous character
            size_t offset_minus_one = edge_.first.offset() - 1;
            if ( offset_minus_one != edge_.space_policy().lower_bound( offset_minus_one, edge_.second.offset() ) ) {
                // offset_minus_one is in the void space
                CTTL_TRACE_TEXT_RESULT( false, '>', m_any_text.c_str() );
                return UniverseT::string_T::npos;
            }

            if ( m_any_text.find( str[ offset_minus_one ] ) != UniverseT::string_T::npos ) {
                // successful match
                CTTL_TRACE_TEXT_RESULT( true, '>', m_any_text.c_str() );
                return edge_.first.offset();
            }
        }

        CTTL_TRACE_TEXT_RESULT( false, '>', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        size_t new_offset = str.find_first_of( m_any_text, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // find ending position
            new_offset = str.find_first_not_of( m_any_text, new_offset );
            if ( new_offset == UniverseT::string_T::npos )
                new_offset = str.length();

            // set ending position
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, '>', m_any_text.c_str() );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, '>', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_ref_end


template< typename StringT >
class xtl_text_first : public xtl_primary< xtl_text_first< StringT > > {

private:
    StringT m_any_text;

public:
    // compile-time

    xtl_text_first( StringT const& any_text_ )
        : m_any_text( any_text_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( m_any_text.find( str[ edge_.first.offset() ] ) != UniverseT::string_T::npos ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();
            // ending position: at least one character in this entity is present
            edge_.first.offset( edge_.first.offset() + 1 );
            CTTL_TRACE_TEXT_RESULT( true, 'F', m_any_text.c_str() );
            return match_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, 'F', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        size_t new_offset = str.find_first_of( m_any_text, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // set find ending position: at least one
            // character in this entity is present
            edge_.first.offset( new_offset + 1 );
            CTTL_TRACE_TEXT_RESULT( true, 'F', m_any_text.c_str() );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, 'F', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_first


template< typename StringT >
class xtl_text_ref_first : public xtl_primary< xtl_text_ref_first< StringT > > {

private:
    StringT const& m_any_text;

public:
    // compile-time

    xtl_text_ref_first( StringT const* str_ptr_ )
        : m_any_text( *str_ptr_ )
    {
    }

    void operator=( xtl_text_ref_first< StringT > const& ) const
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( m_any_text.find( str[ edge_.first.offset() ] ) != UniverseT::string_T::npos ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();
            // ending position: at least one character
            // in this entity is present
            edge_.first.offset( edge_.first.offset() + 1 );
            CTTL_TRACE_TEXT_RESULT( true, 'F', m_any_text.c_str() );
            return match_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, 'F', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        size_t new_offset = str.find_first_of( m_any_text, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // set find ending position: at least one character
            // in this entity is present
            edge_.first.offset( new_offset + 1 );
            CTTL_TRACE_TEXT_RESULT( true, 'F', m_any_text.c_str() );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, 'F', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_ref_first


template< typename StringT >
class xtl_text_entity : public xtl_primary< xtl_text_entity< StringT > > {

private:
    StringT m_any_text;

public:
    // compile-time

    xtl_text_entity( typename StringT::value_type const* any_text_ )
        : m_any_text( any_text_ )
    {
    }

    xtl_text_entity( StringT const& any_text_ )
        : m_any_text( any_text_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( m_any_text.find( str[ edge_.first.offset() ] ) != UniverseT::string_T::npos ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();

            // find ending position
            size_t new_offset = str.find_first_not_of( m_any_text, edge_.first.offset() );
            if ( new_offset == UniverseT::string_T::npos )
                new_offset = str.length();

            // set match ending position
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, '$', m_any_text.c_str() );
            return match_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, '$', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        size_t new_offset = str.find_first_of( m_any_text, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // set find starting position
            size_t match_offset = new_offset;

            // find ending position
            new_offset = str.find_first_not_of( m_any_text, new_offset );
            if ( new_offset == UniverseT::string_T::npos )
                new_offset = str.length();

            // set ending position
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, '$', m_any_text.c_str() );
            return match_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, '$', m_any_text.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_entity


template< typename StringT >
class xtl_text_ref_entity : public xtl_primary< xtl_text_ref_entity< StringT > > {

private:
    StringT const& m_str_ref;

public:
    // compile-time

    xtl_text_ref_entity( StringT const* str_ptr_ )
        : m_str_ref( *str_ptr_ )
    {
    }

    void operator=( xtl_text_ref_entity< StringT > const& ) const
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( m_str_ref.find( str[ edge_.first.offset() ] ) != UniverseT::string_T::npos ) {
            // successful match
            // set match starting position
            size_t match_offset = edge_.first.offset();

            // find ending position
            size_t new_offset = str.find_first_not_of( m_str_ref, edge_.first.offset() );
            if ( new_offset == UniverseT::string_T::npos )
                new_offset = str.length();

            // set match ending position
            edge_.first.offset( new_offset );
            CTTL_TRACE_TEXT_RESULT( true, '$', m_str_ref.c_str() );
            return match_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, '$', m_str_ref.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        size_t new_offset = str.find_first_of( m_str_ref, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // set find starting position
            size_t match_offset = new_offset;

            // find ending position
            new_offset = str.find_first_not_of( m_str_ref, new_offset );
            if ( new_offset == UniverseT::string_T::npos )
                new_offset = str.length();

            edge_.first.offset( new_offset );   // set ending position
            CTTL_TRACE_TEXT_RESULT( true, '$', m_str_ref.c_str() );
            return match_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, '$', m_str_ref.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_ref_entity


template< typename StringT >
class xtl_text_symbol : public xtl_primary< xtl_text_symbol< StringT > > {

private:
    StringT m_text;

public:
    // compile-time

    xtl_text_symbol( StringT const& str_ref_ )
        : m_text( str_ref_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( edge_.first.offset() + m_text.length() <= str.length() ) {
            if ( str.substr( edge_.first.offset(), m_text.length() ) == m_text ) {
                // successful match
                // set match starting position
                size_t match_offset = edge_.first.offset();
                // set match ending position
                edge_.first.offset( edge_.first.offset() + m_text.length() );
                CTTL_TRACE_TEXT_RESULT( true, 'T', m_text.c_str() );
                return match_offset;
            }
        }
        
        CTTL_TRACE_TEXT_RESULT( false, 'T', m_text.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        size_t new_offset = edge_.parent().text().find( m_text, edge_.first.offset() );
        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // set find ending position
            edge_.first.offset( new_offset + m_text.length() );
            CTTL_TRACE_TEXT_RESULT( true, 'T', m_text.c_str() );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, 'T', m_text.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_symbol


template< typename StringT >
class xtl_text_ref_symbol : public xtl_primary< xtl_text_ref_symbol< StringT > > {

private:
    StringT const& m_text_ref;

public:
    // compile-time

    xtl_text_ref_symbol( StringT const* str_ptr_ )
        : m_text_ref( *str_ptr_ )
    {
    }

    void operator=( xtl_text_ref_symbol< StringT > const& )const
    {
    }

    // run-time

    template< typename UniverseT >
    size_t internal_match( UniverseT& edge_ )
    {
        typename UniverseT::string_T const& str = edge_.parent().text();
        if ( edge_.first.offset() + m_text_ref.length() <= str.length() ) {
            if ( str.substr( edge_.first.offset(), m_text_ref.length() ) == m_text_ref ) {
                // successful match
                // set match starting position
                size_t match_offset = edge_.first.offset();
                // set match ending position
                edge_.first.offset( edge_.first.offset() + m_text_ref.length() );
                CTTL_TRACE_TEXT_RESULT( true, 'T', m_text_ref.c_str() );
                return match_offset;
            }
        }

        CTTL_TRACE_TEXT_RESULT( false, 'T', m_text_ref.c_str() );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    size_t internal_find( UniverseT& edge_ )
    {
        size_t new_offset = edge_.parent().text().find(
            m_text_ref,
            edge_.first.offset()
            );

        if ( new_offset != UniverseT::string_T::npos ) {
            // successful find
            // set find ending position
            edge_.first.offset( new_offset + m_text_ref.length() );
            CTTL_TRACE_TEXT_RESULT( true, 'T', m_text_ref.c_str() );
            return new_offset;
        }

        CTTL_TRACE_TEXT_RESULT( false, 'T', m_text_ref.c_str() );
        return UniverseT::string_T::npos;
    }
};  // xtl_text_ref_symbol


class xtl_position_bof {

public:
    // compile-time
    // nothing to do

    // run-time

    template< typename UniverseT >
    static size_t match( UniverseT& edge_ )
    {
        if ( edge_.first.offset() == 0 ) {
            CTTL_TRACE_RESULT( true, 'A' );
            return 0;
        }
        
        CTTL_TRACE_RESULT( false, 'A' );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    static size_t find( UniverseT& edge_ )
    {
        // set beginning of the universe
        edge_.first.offset( 0 );
        CTTL_TRACE_RESULT( true, 'A' );
        return 0;
    }

    template< typename UniverseT >
    static size_t bang_find( UniverseT& edge_ )
    {
        return find( edge_ );
    }

};  // xtl_position_bof


class xtl_position_eof {

public:
    // compile-time
    // nothing to do

    // run-time

    template< typename UniverseT >
    static size_t match( UniverseT& edge_ )
    {
        if ( !edge_.length() ) {
            CTTL_TRACE_STATIC_RESULT( true, 'Z', "EOF" );
            return edge_.second.offset();
        }

        if ( edge_.length() < 0 )
            return find( edge_ );

        // check for void/white space
        size_t saved_first_offset = edge_.space_policy().match( edge_ );

        if ( !edge_.length() ) {
            CTTL_TRACE_STATIC_RESULT( true, 'Z', "EOF" );
            return edge_.second.offset();
        }

        // restore original position
        edge_.first.offset( saved_first_offset );
        CTTL_TRACE_STATIC_RESULT( false, 'Z', "EOF" );
        return UniverseT::string_T::npos;
    }

    template< typename UniverseT >
    static size_t find( UniverseT& edge_ )
    {
        // set find ending position
        edge_.first.offset( edge_.second.offset() );
        CTTL_TRACE_STATIC_RESULT( true, 'Z', "EOF" );
        return edge_.second.offset();
    }

    template< typename UniverseT >
    static size_t bang_find( UniverseT& edge_ )
    {
        return find( edge_ );
    }

};  // xtl_position_eof


template< typename Static_predicateT >
class xtl_predicate {

    Static_predicateT m_predicate;

public:

    xtl_predicate( Static_predicateT const& predicate_ )
        :
        m_predicate( predicate_ )
    {
    }

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_MATCH( 'R' );
        return m_predicate( edge_ );
    }

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_FIND( 'R' );
        edge_.parent().container().m_flags.set( xtl_flag_runtime_find );
        return m_predicate( edge_ );
    }

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_BANG( 'R' );
        edge_.parent().container().m_flags.set( xtl_flag_runtime_bang_find );
        return m_predicate( edge_ );
    }

};  // xtl_predicate


template< typename ObjectT, typename Member_predicateT >
class xtl_member_predicate {

    ObjectT& m_object;

    Member_predicateT m_predicate;

public:

    xtl_member_predicate(
        ObjectT& object_ref_,
        Member_predicateT& predicate_
        )
        :
        m_object( object_ref_ ),
        m_predicate( predicate_ )
    {
    }

    void operator=( xtl_member_predicate< ObjectT, Member_predicateT > const& ) const
    {
    }

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_MATCH( 'R' );
        return std::mem_fun< size_t, ObjectT, UniverseT& >( m_predicate )( &m_object, edge_ );
    }

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_FIND( 'R' );
        edge_.parent().container().m_flags.set( xtl_flag_runtime_find );
        return std::mem_fun< size_t, ObjectT, UniverseT& >( m_predicate )( &m_object, edge_ );
    }

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_BANG( 'R' );
        edge_.parent().container().m_flags.set( xtl_flag_runtime_bang_find );
        return std::mem_fun< size_t, ObjectT, UniverseT& >( m_predicate )( &m_object, edge_ );
    }

};  // xtl_member_predicate


struct xtl_traced_predicate_base {

    int m_line;

    std::string m_rule_name;

    xtl_traced_predicate_base( int line_, char const* rule_name_ )
        :
        m_line( line_ ),
        m_rule_name( rule_name_ )
    {
    }

    template< typename UniverseT >
    void trace_prolog( UniverseT& edge_, char const* mode_ )
    {
        xtl_trace_grammar::depth( +1 );
        std::cout << xtl_trace_grammar::exact_edge2text( edge_, true ).c_str();
        xtl_trace_grammar::build_skyline( '-' );

        std::cout
            << m_line
            << "->"
            << mode_
            << m_rule_name
            << '@'
            << edge_.first.offset()
            << '-'
            << edge_.second.offset()
            << std::endl
            ;
    }

    template< typename UniverseT >
    size_t trace_epilog( UniverseT& edge_, size_t result_ )
    {
        if ( result_ != CTTL_STD_STRING::npos ) {
            size_t begin_offset = result_;
            size_t end_offset = std::min(
                begin_offset + xtl_trace_grammar::fragment_length,
                edge_.first.offset()
                );

            // needed in case if underlying fragment mutates:
            begin_offset = std::min( begin_offset, end_offset );
            end_offset = std::max( begin_offset, end_offset );
            std::string str_temp = edge_.parent().container().text_absolute_substring(
                begin_offset,
                end_offset
                ).c_str();

            std::cout << xtl_trace_grammar::exact_edge2text( edge_, true ).c_str();
            xtl_trace_grammar::build_skyline( '+' );
            std::cout
                << m_line
                << "<-"
                << m_rule_name
                << '@'
                << begin_offset
                << '-'
                << std::max( end_offset, edge_.first.offset() )
                << '\t'
                << '\''
                << xtl_trace_grammar::whitespace2monospace( str_temp )
                << '\''
                << std::endl
                ;

        } else {
            std::cout << xtl_trace_grammar::exact_edge2text( edge_, false ).c_str();
            xtl_trace_grammar::build_skyline( '~' );
            std::cout
                << m_line
                << "<-"
                << m_rule_name
                << '@'
                << edge_.first.offset()
                << std::endl
                ;
        }
        xtl_trace_grammar::depth( -1 );
        return result_;
    }

};  // xtl_traced_predicate_base


template< typename ObjectT, typename Member_predicateT >
class xtl_member_traced_predicate : public xtl_traced_predicate_base {

    ObjectT& m_object;

    Member_predicateT m_predicate;

public:

    xtl_member_traced_predicate(
        int line_,
        char const* rule_name_,
        ObjectT& object_ref_,
        Member_predicateT& predicate_
        )
        :
        xtl_traced_predicate_base( line_, rule_name_ ),
        m_object( object_ref_ ),
        m_predicate( predicate_ )
    {
    }

    void operator=( xtl_member_traced_predicate< ObjectT, Member_predicateT > const& ) const
    {
    }

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        trace_prolog( edge_, "" );
        return trace_epilog(
            edge_,
            std::mem_fun< size_t, ObjectT, UniverseT& >( m_predicate )( &m_object, edge_ )
            );
    }

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        edge_.parent().container().m_flags.set( xtl_flag_runtime_find );
        trace_prolog( edge_, "!" );
        return trace_epilog(
            edge_,
            std::mem_fun< size_t, ObjectT, UniverseT& >( m_predicate )( &m_object, edge_ )
            );
    }

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        edge_.parent().container().m_flags.set( xtl_flag_runtime_bang_find );
        trace_prolog( edge_, "!!" );
        return trace_epilog(
            edge_,
            std::mem_fun< size_t, ObjectT, UniverseT& >( m_predicate )( &m_object, edge_ )
            );
    }

};  // xtl_member_traced_predicate


template< typename Static_predicateT >
class xtl_static_traced_predicate : public xtl_traced_predicate_base {

    Static_predicateT m_predicate;

public:

    xtl_static_traced_predicate(
        int line_,
        char const* rule_name_,
        Static_predicateT const& predicate_
        )
        :
        xtl_traced_predicate_base( line_, rule_name_ ),
        m_predicate( predicate_ )
    {
    }

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        trace_prolog( edge_, "" );
        return trace_epilog( edge_, m_predicate( edge_ ) );
    }

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        edge_.parent().container().m_flags.set( xtl_flag_runtime_find );
        trace_prolog( edge_, "!" );
        return trace_epilog( edge_, m_predicate( edge_ ) );
    }

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        edge_.parent().container().m_flags.set( xtl_flag_runtime_bang_find );
        trace_prolog( edge_, "!!" );
        return trace_epilog( edge_, m_predicate( edge_ ) );
    }

};  // xtl_static_traced_predicate


template< typename Static_predicateT >
inline xtl_wrap< xtl_static_traced_predicate< Static_predicateT > >
xtl_traced_rule( int line_, char const* rule_name_, const Static_predicateT pred_ )
{
    return xtl_wrap< xtl_static_traced_predicate< Static_predicateT > >(
        xtl_static_traced_predicate< Static_predicateT >(
            line_,
            rule_name_,
            pred_
            )
        );
}

template< typename ObjectT, typename PredicateT >
inline xtl_wrap< xtl_member_traced_predicate< ObjectT, PredicateT > >
xtl_traced_rule( int line_, char const* rule_name_, ObjectT& object_ref_, PredicateT pred_ )
{
    return xtl_wrap< xtl_member_traced_predicate< ObjectT, PredicateT > >(
        xtl_member_traced_predicate< ObjectT, PredicateT >(
            line_,
            rule_name_,
            object_ref_,
            pred_ 
            )
        );
}

}   // namespace cttl_impl

#endif // _CTTL_XTL_PRIMARY_H_INCLUDED_

---