xtl_op_impl.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_op_impl.h

#ifndef _CTTL_XTL_OP_IMPL_H_INCLUDED_
#define _CTTL_XTL_OP_IMPL_H_INCLUDED_

namespace cttl_impl {

// Base implementation classes for overloaded operators

template< typename ExprT >
class xtl_op_base_unary {

protected:
    ExprT m_expr;

public:
    // compile-time

    xtl_op_base_unary( ExprT const& expr_ )
    : m_expr( expr_ )
    {
    }

protected:
    template< typename UniverseT >
    size_t kleene_list( UniverseT& edge_, size_t upper_limit_ = 0 )
    {

        // if this offset stops progressing, we must bail out of infinite loop
        typename UniverseT::offset_manager_T iteration_offset( edge_.parent().container(), UniverseT::string_T::npos );
        typename UniverseT::offset_manager_T match_offset( edge_.parent().container(), UniverseT::string_T::npos );

        // statically captured offset to watch mutablility of the universe.
        // universe is considered mutated if saved_end_offset no longer matches the end of the universe.
        size_t saved_end_offset = edge_.second.offset();

        size_t cnt = 0;
        while ( ( match_offset = m_expr.match( edge_ ) ) != UniverseT::string_T::npos ) {
            // If universe is mutable and the user deleted matched fragment,
            // edge_.first.offset() is brought back, therefore, it will appear here
            // as an empty (epsilon) match. In such case, if universe has mutated,
            // the search should continue.

            // Check if the universe has mutated:
            if ( saved_end_offset == edge_.second.offset() ) {
                if ( iteration_offset == edge_.first.offset() ) {
                    CTTL_TRACE_TEXT( 'i', "kleene_list: iteration made no progress: bailing out" );
                    break;  // second, third, etc., iteration hasn't made any progress: bail out
                }

                ++cnt;

                if ( match_offset == edge_.first.offset() ) {
                    // second, third, etc., iteration succeeded on an empty substring,
                    // do not count it as a match, bail out of the loop:
                    CTTL_TRACE_TEXT( 'i', "kleene_list: epsilon match: bailing out" );
                    break;
                }

            } else {
                ++cnt;
                saved_end_offset = edge_.second.offset();
            }

            if ( upper_limit_ && ( cnt == upper_limit_ ) ) {
                CTTL_TRACE_TEXT( 'i', "kleene_list: user-specified match limit: bailing out" );
                break;
            }

            iteration_offset = edge_.first.offset();
        }
        return cnt;
    }

};  // xtl_op_base_unary


template< typename Left_exprT, typename Right_exprT >
class xtl_op_base_binary {

protected:
    Left_exprT m_expr_lhs;

    Right_exprT m_expr_rhs;

public:

    // compile-time

    xtl_op_base_binary( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
    : m_expr_lhs( lhs_expr_ ), m_expr_rhs( rhs_expr_ )
    {
    }

};  // xtl_op_base_binary


// Implementation classes for unary operators

template< typename ExprT >
struct xtl_opunarbang : public xtl_op_base_unary< ExprT > {

    // compile-time

    xtl_opunarbang( ExprT const& expr_ )
    : xtl_op_base_unary< ExprT >( expr_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_MATCH( '!' );
        return this->m_expr.find( edge_ );
    }
    
    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_FIND( '!' );
        return this->m_expr.bang_find( edge_ );
    }
    
    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_BANG( '!' );
        return this->m_expr.bang_find( edge_ );
    }

};  // xtl_opunarbang


template< typename ExprT >
class xtl_opunarstar : public xtl_op_base_unary< ExprT > {

protected:

    size_t m_upper_limit;

public:
    // compile-time

    xtl_opunarstar( ExprT const& expr_, size_t upper_limit_ = 0 )
    : xtl_op_base_unary< ExprT >( expr_ ), m_upper_limit( upper_limit_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // [R,R,R,...]_ kleene star
        CTTL_TRACE_LEVEL_MATCH( '*' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );

        // statically captured offset to watch mutablility of the universe.
        // universe is considered mutated if saved_end_offset no longer matches the end of the universe.
        size_t saved_end_offset = edge_.second.offset();
        typename UniverseT::offset_manager_T match_offset( edge_.parent().container(), this->m_expr.match( edge_ ) );

        if ( match_offset != UniverseT::string_T::npos ) {
            // If universe is mutable and the user deleted matched fragment,
            // edge_.first.offset() is brought back, therefore, it will appear here
            // as an empty (epsilon) match. In such case, if universe has mutated,
            // the search should continue.

            // Check if the universe has mutated:
            if ( saved_end_offset == edge_.second.offset() ) {
                if ( saved_first_offset == edge_.first.offset() ) {
                    // one match aleady found, no universe progress was made.
                    // No more match attemts necessary, we are done:
                    return match_offset;
                }
            }

            if ( m_upper_limit ) {
                // user wants to use upper limit on the number of matches
                // minus one accounts for the expression already found

                if ( m_upper_limit == 1 ) {
                    // one is a special case: if upper limit is one, then
                    // there is no need to search for more instances
                    return match_offset;
                }

                // it is sufficient to find only
                // zero to (m_upper_limit - 1) matches:
                kleene_list( edge_, m_upper_limit - 1 );

            } else
                // user doesn't care how many matches are found:
                kleene_list( edge_ );

        } else {
            // success offset is at the current position
            //assert( saved_first_offset == edge_.first.offset() );
            return saved_first_offset;
        }

        return match_offset;
    }
    
    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        // [!R,R,R,...]_ kleene star
        CTTL_TRACE_LEVEL_FIND( '*' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );

        // statically captured offset to watch mutablility of the universe.
        // universe is considered mutated if saved_end_offset no
        // longer matches the end of the universe.
        size_t saved_end_offset = edge_.second.offset();
        typename UniverseT::offset_manager_T match_offset( edge_.parent().container(), this->m_expr.find( edge_ ) );

        if ( match_offset != UniverseT::string_T::npos ) {
            // If universe is mutable and the user deleted matched fragment,
            // edge_.first.offset() is brought back, therefore, it will appear here
            // as an empty (epsilon) match. In such case, if universe has mutated,
            // the search should go on.
            // Check if the universe mutated:
            if ( saved_end_offset == edge_.second.offset() ) {
                if ( saved_first_offset == edge_.first.offset() ) {
                    // one match aleady found, no universe progress was made.
                    // No more match attemts necessary, we are done:
                    return match_offset;
                }
            }

            if ( m_upper_limit ) {
                // user wants to use upper limit on the number of matches
                // minus one accounts for the expression already found

                if ( m_upper_limit == 1 ) {
                    // one is a special case: if upper limit is one, then
                    // there is no need to search for more instances
                    return match_offset;
                }

                // it is sufficient to find
                // zero to (m_upper_limit - 1) more matches:
                kleene_list( edge_, m_upper_limit - 1 );

            } else
                // user doesn't care how many matches are found:
                kleene_list( edge_ );

        } else {
            // success offset is at the current position
            //assert( saved_first_offset == edge_.first.offset() );
            return saved_first_offset;
        }

        return match_offset;
    }
    
    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        // [!!R,R,R,...]_ kleene star
        CTTL_TRACE_LEVEL_BANG( '*' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        // statically captured offset to watch mutablility of the universe.
        // universe is considered mutated if saved_end_offset no
        // longer matches the end of the universe.
        size_t saved_end_offset = edge_.second.offset();
        typename UniverseT::offset_manager_T match_offset( edge_.parent().container(), this->m_expr.bang_find( edge_ ) );

        if ( match_offset != UniverseT::string_T::npos ) {
            // If universe is mutable and the user deleted matched fragment,
            // edge_.first.offset() is brought back, therefore, it will appear here
            // as an empty (epsilon) match. In such case, if universe has mutated,
            // the search should go on.
            
            // Check if the universe mutated:
            if ( saved_end_offset == edge_.second.offset() ) {
                if ( saved_first_offset == edge_.first.offset() ) {
                    // one match aleady found, no universe progress was made.
                    // No more match attemts necessary, we are done:
                    return match_offset;
                }
            }

            if ( m_upper_limit ) {
                // user wants to use upper limit on the number of matches
                // minus one accounts for the expression already found

                if ( m_upper_limit == 1 ) {
                    // one is a special case: if upper limit is one, then
                    // there is no need to search for more instances
                    return match_offset;
                }

                // it is sufficient to find
                // zero to (m_upper_limit - 1) more matches:
                kleene_list( edge_, m_upper_limit - 1 );

            } else
                // user doesn't care how many matches are found:
                kleene_list( edge_ );

        } else {
            // success offset is at the current position
            //assert( saved_first_offset == edge_.first.offset() );
            return saved_first_offset;
        }

        return match_offset;
    }

};  // xtl_opunarstar


template< typename ExprT >
class xtl_opunarminus : public xtl_op_base_unary< ExprT > {

public:
    // compile-time

    xtl_opunarminus( ExprT const& expr_ )
    : xtl_op_base_unary< ExprT >( expr_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // -R_ logical not
        CTTL_TRACE_LEVEL_MATCH( '-' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        size_t match_offset = this->m_expr.match( edge_ );

        if ( match_offset != UniverseT::string_T::npos ) {
            // encapsulated expression succeeded, we fail:
            // restore universe
            edge_.first.offset( saved_first_offset );
            CTTL_TRACE_RESULT( false, '-' );
            return UniverseT::string_T::npos;
        }

        // success offset is at the current position
        //assert( saved_first_offset == edge_.first.offset() );
        return saved_first_offset;
    }
    

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        // -!R_ logical not
        CTTL_TRACE_LEVEL_FIND( '-' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        size_t match_offset = this->m_expr.find( edge_ );

        if ( match_offset != UniverseT::string_T::npos ) {
            // encapsulated expression succeeded, we fail:
            // restore universe
            edge_.first.offset( saved_first_offset );
            CTTL_TRACE_RESULT( false, '-' );
            return UniverseT::string_T::npos;
        }

        // success offset is at the current position
        //assert( saved_first_offset == edge_.first.offset() );
        return saved_first_offset;
    }
    

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        // -!!R_ logical not
        CTTL_TRACE_LEVEL_BANG( '-' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        size_t match_offset = this->m_expr.bang_find( edge_ );

        if ( match_offset != UniverseT::string_T::npos ) {
            // encapsulated expression succeeded, we fail:
            // restore universe
            edge_.first.offset( saved_first_offset );
            CTTL_TRACE_RESULT( false, '-' );
            return UniverseT::string_T::npos;
        }

        // success offset is at the current position
        //assert( saved_first_offset == edge_.first.offset() );
        return saved_first_offset;
    }

};  // xtl_opunarminus


template< typename ExprT >
class xtl_opunarplus : public xtl_op_base_unary< ExprT > {

protected:
    size_t m_upper_limit;

    size_t m_lower_limit;

    template< typename UniverseT >
    size_t unarplus( UniverseT& edge_, size_t saved_end_offset_, size_t first_match_offset_ )
    {
        typename UniverseT::offset_manager_T match_offset( edge_.parent().container(), first_match_offset_ );
        
        if ( match_offset != UniverseT::string_T::npos ) {
            // If universe is mutable and the user deleted matched fragment,
            // edge_.first.offset() is brought back, therefore, it will appear here
            // as an empty (epsilon) match. In such case, if universe has mutated,
            // the search should continue.
            // Check if the universe has mutated:
            if ( saved_end_offset_ == edge_.second.offset() ) {
                if ( match_offset == edge_.first.offset() ) {
                    // one match aleady found, no universe progress was made.
                    // No more match attemts necessary, we are done:
                    if ( !m_upper_limit )
                        return match_offset;

                    if ( ( m_lower_limit <= 1 ) && ( 1 <= m_upper_limit ) )
                        return match_offset;

                    CTTL_TRACE_TEXT_RESULT( false, '+', "kleene plus: too few matches (one epsilon found)" );
                    return UniverseT::string_T::npos;
                }
            }

            if ( m_upper_limit ) {
                if ( m_upper_limit == 1 )
                    // case: expr + m_upper_limit, where m_upper_limit == 1
                    return match_offset;

                // user wants to use upper limit on the number of matches
                // plus one accounts for the expression already found
                if ( m_lower_limit ) {
                    // case: expr + pair( m_lower_limit, m_upper_limit )
                    size_t cnt = kleene_list( edge_, m_upper_limit ) + 1;
                    if ( cnt > m_upper_limit ) {
                        CTTL_TRACE_TEXT_RESULT( false, '+', "kleene plus: too many matches" );
                        return UniverseT::string_T::npos;

                    }

                    if ( cnt < m_lower_limit ) {
                        // user also wants to use lower limit on the number of matches
                        CTTL_TRACE_TEXT_RESULT( false, '+', "kleene plus: too few matches" );
                        return UniverseT::string_T::npos;
                    }

                } else {
                    // case: expr + m_upper_limit, where m_upper_limit > 1
                    // it is sufficient to find up to (m_upper_limit - 1) more matches:
                    kleene_list( edge_, m_upper_limit - 1 );
                }

            } else
                // case: +expr
                // user doesn't care how many matches are found:
                kleene_list( edge_ );

            return match_offset;
        }

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

public:

    // compile-time

    xtl_opunarplus( ExprT const& expr_, size_t upper_limit_ = 0, size_t lower_limit_ = 0 )
    : xtl_op_base_unary< ExprT >( expr_ ), m_upper_limit( upper_limit_ ), m_lower_limit( lower_limit_ )
    {
    }


    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // [R,R,R,...]_ kleene plus
        CTTL_TRACE_LEVEL_MATCH( '+' );
        size_t saved_end_offset = edge_.second.offset();
        return unarplus( edge_, saved_end_offset, this->m_expr.match( edge_ ) );
    }
    

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        // [!R,R,R,...]_ kleene plus
        CTTL_TRACE_LEVEL_FIND( '+' );
        size_t saved_end_offset = edge_.second.offset();
        return unarplus( edge_, saved_end_offset, this->m_expr.find( edge_ ) );
    }
    

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        // [!!R,R,R,...]_ kleene plus
        CTTL_TRACE_LEVEL_BANG( '+' );
        size_t saved_end_offset = edge_.second.offset();
        return unarplus( edge_, saved_end_offset, this->m_expr.bang_find( edge_ ) );
    }

};  // xtl_opunarplus


template< typename ExprT >
struct xtl_entity : public xtl_op_base_unary< ExprT > {

    // compile-time

    xtl_entity( ExprT const& expr_ )
    : xtl_op_base_unary< ExprT >( expr_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_MATCH( 'E' );
        typename UniverseT::offset_manager_T match_offset( edge_.parent().container(), this->m_expr.match( edge_ ) );
        if ( ( match_offset != UniverseT::string_T::npos ) && ( match_offset != edge_.first.offset() ) )
            return match_offset;

        return UniverseT::string_T::npos;
    }
    

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_FIND( 'E' );
        typename UniverseT::offset_manager_T match_offset( edge_.parent().container(), this->m_expr.find( edge_ ) );
        if ( ( match_offset != UniverseT::string_T::npos ) && ( match_offset != edge_.first.offset() ) )
            return match_offset;

        return UniverseT::string_T::npos;
    }
    

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        CTTL_TRACE_LEVEL_BANG( 'E' );
        typename UniverseT::offset_manager_T match_offset( edge_.parent().container(), this->m_expr.bang_find( edge_ ) );
        if ( ( match_offset != UniverseT::string_T::npos ) && ( match_offset != edge_.first.offset() ) )
            return match_offset;

        return UniverseT::string_T::npos;
    }

};  // xtl_entity


// Implementation classes for binary operators

template< typename Left_exprT, typename Right_exprT >
struct xtl_opbinplus : public xtl_op_base_binary< Left_exprT, Right_exprT > {

    // compile-time

    xtl_opbinplus( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
    : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // L+R_ relaxed sequence
        // if L succeeds, and R fails, universe needs to be restored
        CTTL_TRACE_LEVEL_MATCH( ';' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.match( edge_ ) );
        
        if (
            ( match_lhs_offset != UniverseT::string_T::npos )
            &&
            ( this->m_expr_rhs.match( edge_ ) != UniverseT::string_T::npos )
            )
                return match_lhs_offset;

        // restore universe
        edge_.first.offset( saved_first_offset );
        return UniverseT::string_T::npos;
    }


    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        // !L+R_
        CTTL_TRACE_LEVEL_FIND( ';' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.find( edge_ ) );

        if (
            ( match_lhs_offset != UniverseT::string_T::npos )
            &&
            ( this->m_expr_rhs.match( edge_ ) != UniverseT::string_T::npos )
            )
                return match_lhs_offset;

        edge_.first.offset( saved_first_offset );       // restore universe
        return UniverseT::string_T::npos;
    }
    

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        // !!L+R_
        CTTL_TRACE_LEVEL_BANG( ';' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), UniverseT::string_T::npos );
        // if this offset stops progressing, we must bail out of infinite loop:
        typename UniverseT::offset_manager_T iteration_offset( edge_.parent().container(), UniverseT::string_T::npos );

        while ( ( match_lhs_offset = this->m_expr_lhs.bang_find( edge_ ) ) != UniverseT::string_T::npos ) {
            if ( this->m_expr_rhs.match( edge_ ) != UniverseT::string_T::npos )
                return match_lhs_offset;

            if ( iteration_offset == edge_.first.offset() ) {
                CTTL_TRACE_TEXT( '+', "!!expr + expr: iteration has not made any progress: bailing out" );
                break;  // second, third, etc., iteration hasn't made any progress: bail out
            }

            iteration_offset = edge_.first.offset();
        }

        // restore universe
        edge_.first.offset( saved_first_offset );
        return UniverseT::string_T::npos;
    }

};  // xtl_opbinplus


template< typename Left_exprT, typename Right_exprT >
struct xtl_opbinpipe : public xtl_op_base_binary< Left_exprT, Right_exprT > {
    // implements behavior of binary expr | expr operator

    // compile-time

    xtl_opbinpipe( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
    : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // (L|R)_ logical "if L; else R;"
        // first-of( L, R )_
        CTTL_TRACE_LEVEL_MATCH( '|' );
        size_t match_offset = this->m_expr_lhs.match( edge_ );
        if ( match_offset != UniverseT::string_T::npos )
            return match_offset;

        match_offset = this->m_expr_rhs.match( edge_ );
        if ( match_offset != UniverseT::string_T::npos )
            return match_offset;

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

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        // ( !L | !R )_
        // first-of( !L, !R )_
        CTTL_TRACE_LEVEL_FIND( '|' );
        size_t match_offset = this->m_expr_lhs.find( edge_ );
        if ( match_offset != UniverseT::string_T::npos )
            return match_offset;

        match_offset = this->m_expr_rhs.find( edge_ );
        if ( match_offset != UniverseT::string_T::npos )
            return match_offset;

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

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        // ( !!L | !!R )_
        // first-of( !!L, !!R )_
        CTTL_TRACE_LEVEL_BANG( '|' );
        size_t match_offset = this->m_expr_lhs.bang_find( edge_ );
        if ( match_offset != UniverseT::string_T::npos )
            return match_offset;

        match_offset = this->m_expr_rhs.bang_find( edge_ );
        if ( match_offset != UniverseT::string_T::npos )
            return match_offset;

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

};  // xtl_opbinpipe


template< typename Left_exprT, typename Right_exprT >
struct xtl_opbin2pipe : public xtl_op_base_binary< Left_exprT, Right_exprT > {

    // compile-time

    xtl_opbin2pipe( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
    : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
    {
    }

    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // ( L || R )_
        // first-of( nearest-of( !L, !R ), longest-of( !L, !R ) )_
        CTTL_TRACE_LEVEL_MATCH( '|' );

        xtl_edge_offset_manager< UniverseT > saved_lhs_edge( edge_ );

        // position of the left side of the universe after LHS succeeds:
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.match( edge_ ) );
        if ( match_lhs_offset != UniverseT::string_T::npos )
            // LHS succeeded
            // save current position and restart search from the same position
            saved_lhs_edge.swap( edge_ );

        // position of the right side of the universe after RHS expression succeeds:
        typename UniverseT::offset_manager_T match_rhs_offset( edge_.parent().container(), this->m_expr_rhs.match( edge_ ) );
        if ( match_rhs_offset != UniverseT::string_T::npos ) {
            // RHS succeeded
            if ( match_lhs_offset == UniverseT::string_T::npos )
                // F,T case
                return match_rhs_offset;

            // T,T case
            // find longest-of( L, R ) )_
            if (
                ( match_lhs_offset == match_rhs_offset )
                &&
                ( /*lhs_length*/saved_lhs_edge.first - match_lhs_offset < /*rhs_length*/edge_.first.offset() - match_rhs_offset )
                )
                // RHS is longer
                return match_rhs_offset;

            // find nearest-of( L, R )
            else if ( match_rhs_offset < match_lhs_offset )
                // RHS is closer
                return match_rhs_offset;

            // LHS is closer or longer, or has exactly the same size and location
        }

        if ( match_lhs_offset != UniverseT::string_T::npos ) {
            // LHS succeeded
            // T,F case
            saved_lhs_edge.restore( edge_ );
            return match_lhs_offset;
        }

        // F,F case
        // note that because both sides have failed, they already restored original universe
        CTTL_TRACE_TEXT_RESULT( false, '|', "||" );
        return UniverseT::string_T::npos;
    }   // match()
    
    
    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        // ( !L || !R )_
        // first-of( nearest-of( !L, !R ), longest-of( !L, !R ) )_
        CTTL_TRACE_LEVEL_FIND( '|' );

        xtl_edge_offset_manager< UniverseT > saved_lhs_edge( edge_ );

        // position of the left side of the universe after LHS succeeds:
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.find( edge_ ) );
        if ( match_lhs_offset != UniverseT::string_T::npos )
            // LHS succeeded
            // save current position and restart search from the same position
            saved_lhs_edge.swap( edge_ );

        // position of the right side of the universe after RHS expression succeeds:
        typename UniverseT::offset_manager_T match_rhs_offset( edge_.parent().container(), this->m_expr_rhs.find( edge_ ) );
        if ( match_rhs_offset != UniverseT::string_T::npos ) {
            // RHS succeeded
            if ( match_lhs_offset == UniverseT::string_T::npos )
                // F,T case
                return match_rhs_offset;

            // T,T case
            // find longest-of( !L, !R ) )_
            if (
                ( match_lhs_offset == match_rhs_offset )
                &&
                ( /*lhs_length*/saved_lhs_edge.first - match_lhs_offset < /*rhs_length*/edge_.first.offset() - match_rhs_offset )
                )
                // RHS is longer
                return match_rhs_offset;

            // find nearest-of( !L, !R )
            else if ( match_rhs_offset < match_lhs_offset )
                // RHS is closer
                return match_rhs_offset;

            // LHS is closer or longer, or has exactly the same size and location.
            // if so, LHS is the answer
        }

        if ( match_lhs_offset != UniverseT::string_T::npos ) {
            // LHS succeeded
            // T,F case
            saved_lhs_edge.restore( edge_ );
            return match_lhs_offset;
        }

        // F,F case
        // note that because both sides have failed, they already restored original universe
        CTTL_TRACE_TEXT_RESULT( false, '|', "||" );
        return UniverseT::string_T::npos;

    }   // find()
    

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        // ( !!L || !!R )_
        // first-of( nearest-of( !!L, !!R ), longest-of( !!L, !!R ) )_
        CTTL_TRACE_LEVEL_BANG( '|' );
        xtl_edge_offset_manager< UniverseT > saved_lhs_edge( edge_ );

        // position of the left side of the universe after LHS succeeds:
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.bang_find( edge_ ) );
        if ( match_lhs_offset != UniverseT::string_T::npos )
            // LHS succeeded
            // save current position and restart search from the same position
            saved_lhs_edge.swap( edge_ );

        // position of the right side of the universe after RHS expression succeeds:
        typename UniverseT::offset_manager_T match_rhs_offset( edge_.parent().container(), this->m_expr_rhs.bang_find( edge_ ) );
        if ( match_rhs_offset != UniverseT::string_T::npos ) {
            // RHS succeeded
            if ( match_lhs_offset == UniverseT::string_T::npos )
                // F,T case
                return match_rhs_offset;

            // T,T case
            // longest-of( !!L, !!R ) )_
            if (
                ( match_lhs_offset == match_rhs_offset )
                &&
                ( /*lhs_length*/saved_lhs_edge.first - match_lhs_offset < /*rhs_length*/edge_.first.offset() - match_rhs_offset )
                )
                // RHS is longer
                return match_rhs_offset;

            // nearest-of( !!L, !!R )
            else if ( match_rhs_offset < match_lhs_offset )
                // RHS is closer
                return match_rhs_offset;

            // LHS is closer or longer, or has exactly the same size and location.
            // if so, LHS is the answer
        }

        if ( match_lhs_offset != UniverseT::string_T::npos ) {
            // LHS succeeded
            // T,F case
            saved_lhs_edge.restore( edge_ );
            return match_lhs_offset;
        }

        // F,F case
        // note that because both sides have failed, they already restored original universe
        CTTL_TRACE_TEXT_RESULT( false, '|', "||" );
        return UniverseT::string_T::npos;

    }   // bang_find()

};  // xtl_opbin2pipe


template< typename Left_exprT, typename Right_exprT >
struct xtl_opbinconcat : public xtl_op_base_binary< Left_exprT, Right_exprT > {

    // compile-time

    xtl_opbinconcat( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
    : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
    {
    }


    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // L^R_ strict sequence
        // if L succeeds, and R fails, universe needs to be restored
        CTTL_TRACE_LEVEL_MATCH( '^' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        // saved_lhs_offset is required because LHS and RHS can be the same object:
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.match( edge_ ) );

        if ( match_lhs_offset != UniverseT::string_T::npos ) {
            typename UniverseT::strict_edge_T strict_universe( edge_ );
            if ( this->m_expr_rhs.match( strict_universe ) != UniverseT::string_T::npos )
                return match_lhs_offset;
        }

        edge_.first.offset( saved_first_offset );       // restore universe
        CTTL_TRACE_RESULT( false, '^' );
        return UniverseT::string_T::npos;
    }
    

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        // !L^R_
        CTTL_TRACE_LEVEL_FIND( '^' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        // saved_lhs_offset is required because LHS and RHS can be the same object:
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.find( edge_ ) );

        if ( match_lhs_offset != UniverseT::string_T::npos ) {
            typename UniverseT::strict_edge_T strict_universe( edge_ );
            if ( this->m_expr_rhs.match( strict_universe ) != UniverseT::string_T::npos )
                return match_lhs_offset;
        }

        edge_.first.offset( saved_first_offset );       // restore universe
        CTTL_TRACE_RESULT( false, '^' );
        return UniverseT::string_T::npos;
    }
    

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        // !!L^R_
        CTTL_TRACE_LEVEL_BANG( '^' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), UniverseT::string_T::npos );
        // if this offset stops progressing, we must bail out of infinite loop:
        typename UniverseT::offset_manager_T iteration_offset( edge_.parent().container(), UniverseT::string_T::npos );

        while ( ( match_lhs_offset = this->m_expr_lhs.bang_find( edge_ ) ) != UniverseT::string_T::npos ) {
            typename UniverseT::strict_edge_T strict_universe( edge_ );
            if ( this->m_expr_rhs.match( strict_universe ) != UniverseT::string_T::npos )
                return match_lhs_offset;

            if ( iteration_offset == edge_.first.offset() ) {
                CTTL_TRACE_TEXT( '^', "!!expr ^ expr: iteration has not made any progress: bailing out" );
                break;  // second, third, etc., iteration hasn't made any progress: bail out
            }

            iteration_offset = edge_.first.offset();
        }

        edge_.first.offset( saved_first_offset );       // restore universe
        CTTL_TRACE_RESULT( false, '^' );
        return UniverseT::string_T::npos;
    }

};  // xtl_opbinconcat


template< typename Left_exprT, typename Right_exprT >
struct xtl_opbinminus : public xtl_op_base_binary< Left_exprT, Right_exprT > {

    // compile-time

    xtl_opbinminus( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
    : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
    {
    }


    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // L-R_ strict set-difference
        // if L succeeds, and R fails, universe needs to be restored
        CTTL_TRACE_LEVEL_MATCH( '-' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        xtl_edge_offset_manager< UniverseT > saved_lhs_edge( edge_ );   // preserve current universe

        // position of the left side of the universe after LHS succeeds:
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.match( edge_ ) );
        if ( match_lhs_offset != UniverseT::string_T::npos ) {
            saved_lhs_edge.save( edge_ );                   // preserve LHS edge
            edge_.second.offset( edge_.first.offset() );    // restrict RHS universe
            edge_.first.offset( match_lhs_offset );
            typename UniverseT::strict_edge_T strict_universe( edge_ );
            if ( this->m_expr_rhs.match( strict_universe ) == UniverseT::string_T::npos ) {
                // RHS did not match, we succeed:
                saved_lhs_edge.restore( edge_ );        // restore LHS edge
                return match_lhs_offset;
            }
        }

        // RHS matched, we fail:
        edge_.first.offset( saved_first_offset );       // restore universe
        edge_.second.offset( saved_lhs_edge.second );
        CTTL_TRACE_RESULT( false, '-' );
        return UniverseT::string_T::npos;
    }
    

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        // !L-R_
        CTTL_TRACE_LEVEL_FIND( '-' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        xtl_edge_offset_manager< UniverseT > saved_lhs_edge( edge_ );   // preserve current universe

        // position of the left side of the universe after LHS succeeds:
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.find( edge_ ) );
        if ( match_lhs_offset != UniverseT::string_T::npos ) {
            saved_lhs_edge.save( edge_ );                   // preserve LHS edge
            edge_.second.offset( edge_.first.offset() );    // restrict RHS universe
            edge_.first.offset( match_lhs_offset );
            typename UniverseT::strict_edge_T strict_universe( edge_ );
            if ( this->m_expr_rhs.match( strict_universe ) == UniverseT::string_T::npos ) {
                // RHS did not match, we succeed:
                saved_lhs_edge.restore( edge_ );            // restore LHS edge
                return match_lhs_offset;
            }
        }

        // RHS matched, we fail:
        edge_.first.offset( saved_first_offset );       // restore universe
        edge_.second.offset( saved_lhs_edge.second );
        CTTL_TRACE_RESULT( false, '-' );
        return UniverseT::string_T::npos;
    }


    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        // !!(L_-R)
        CTTL_TRACE_LEVEL_BANG( '-' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), UniverseT::string_T::npos );
        xtl_edge_offset_manager< UniverseT > saved_lhs_edge( edge_ );   // preserve current universe
        // if this offset stops progressing, we must bail out of infinite loop:
        typename UniverseT::offset_manager_T iteration_offset( edge_.parent().container(), UniverseT::string_T::npos );

        while ( ( match_lhs_offset = this->m_expr_lhs.bang_find( edge_ ) ) != UniverseT::string_T::npos ) {
            saved_lhs_edge.save( edge_ );                   // preserve LHS edge
            edge_.second.offset( edge_.first.offset() );    // restrict RHS universe
            edge_.first.offset( match_lhs_offset );
            typename UniverseT::strict_edge_T strict_universe( edge_ );
            if ( this->m_expr_rhs.match( strict_universe ) == UniverseT::string_T::npos ) {
                // RHS did not match, we succeed:
                saved_lhs_edge.restore( edge_ );            // restore LHS edge
                return match_lhs_offset;
            }

            // RHS matched, continue searching:
            saved_lhs_edge.restore( edge_ );                // restore LHS edge

            if ( iteration_offset == edge_.first.offset() ) {
                CTTL_TRACE_TEXT( '-', "!!expr - expr: iteration has not made any progress: bailing out" );
                break;  // second, third, etc., iteration hasn't made any progress: bail out
            }

            iteration_offset = edge_.first.offset();
        }

        edge_.first.offset( saved_first_offset );       // restore universe
        CTTL_TRACE_RESULT( false, '-' );
        return UniverseT::string_T::npos;
    }

};  // xtl_opbinminus


template< typename Left_exprT, typename Right_exprT >
struct xtl_opbinand : public xtl_op_base_binary< Left_exprT, Right_exprT > {

    // compile-time

    xtl_opbinand( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
    : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
    {
    }


    // run-time

    template< typename UniverseT >
    size_t match( UniverseT& edge_ )
    {
        // L&R_ strict set-intersection
        // if L succeeds, and R fails, universe needs to be restored
        CTTL_TRACE_LEVEL_MATCH( '&' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        xtl_edge_offset_manager< UniverseT > saved_lhs_edge( edge_ );   // preserve current universe

        // position of the left side of the universe after LHS succeeds:
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.match( edge_ ) );
        if ( match_lhs_offset != UniverseT::string_T::npos ) {
            saved_lhs_edge.save( edge_ );                   // preserve LHS edge
            edge_.second.offset( edge_.first.offset() );    // restrict RHS universe
            edge_.first.offset( match_lhs_offset );
            typename UniverseT::strict_edge_T strict_universe( edge_ );
            if ( this->m_expr_rhs.match( strict_universe ) != UniverseT::string_T::npos ) {
                // LHS & RHS intersection succeeded
                saved_lhs_edge.restore( edge_ );        // restore LHS edge
                return match_lhs_offset;
            }
        }

        edge_.first.offset( saved_first_offset );       // restore universe
        edge_.second.offset( saved_lhs_edge.second );
        CTTL_TRACE_RESULT( false, '&' );
        return UniverseT::string_T::npos;
    }
    

    template< typename UniverseT >
    size_t find( UniverseT& edge_ )
    {
        // !L&R_
        CTTL_TRACE_LEVEL_FIND( '&' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        xtl_edge_offset_manager< UniverseT > saved_lhs_edge( edge_ );   // preserve current universe

        // position of the left side of the universe after LHS succeeds:
        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), this->m_expr_lhs.find( edge_ ) );
        if ( match_lhs_offset != UniverseT::string_T::npos ) {
            saved_lhs_edge.save( edge_ );                   // preserve LHS edge
            edge_.second.offset( edge_.first.offset() );    // restrict RHS universe
            edge_.first.offset( match_lhs_offset );
            typename UniverseT::strict_edge_T strict_universe( edge_ );
            if ( this->m_expr_rhs.match( strict_universe ) != UniverseT::string_T::npos ) {
                // LHS & RHS intersection succeeded
                saved_lhs_edge.restore( edge_ );            // restore LHS edge
                return match_lhs_offset;
            }
        }

        edge_.first.offset( saved_first_offset );       // restore universe
        edge_.second.offset( saved_lhs_edge.second );
        CTTL_TRACE_RESULT( false, '&' );
        return UniverseT::string_T::npos;
    }
    

    template< typename UniverseT >
    size_t bang_find( UniverseT& edge_ )
    {
        // !!L&R_
        CTTL_TRACE_LEVEL_BANG( '&' );
        typename UniverseT::offset_manager_T saved_first_offset( edge_.parent().container(), edge_.first.offset() );
        xtl_edge_offset_manager< UniverseT > saved_lhs_edge( edge_ );   // preserve current universe
        // if this offset stops progressing, we must bail out of infinite loop:
        typename UniverseT::offset_manager_T iteration_offset( edge_.parent().container(), UniverseT::string_T::npos );

        typename UniverseT::offset_manager_T match_lhs_offset( edge_.parent().container(), UniverseT::string_T::npos );
        while ( ( match_lhs_offset = this->m_expr_lhs.bang_find( edge_ ) ) != UniverseT::string_T::npos ) {
            saved_lhs_edge.save( edge_ );                   // preserve LHS edge
            edge_.second.offset( edge_.first.offset() );    // restrict RHS universe
            edge_.first.offset( match_lhs_offset );
            typename UniverseT::strict_edge_T strict_universe( edge_ );
            if ( this->m_expr_rhs.match( strict_universe ) != UniverseT::string_T::npos ) {
                // LHS & RHS intersection succeeded
                saved_lhs_edge.restore( edge_ );            // restore LHS edge
                return match_lhs_offset;
            }

            // RHS did not match, continue searching:
            saved_lhs_edge.restore( edge_ );                // restore LHS edge

            if ( iteration_offset == edge_.first.offset() ) {
                CTTL_TRACE_TEXT( '&', "!!expr & expr: iteration has not made any progress: bailing out" );
                break;  // second, third, etc., iteration hasn't made any progress: bail out
            }

            iteration_offset = edge_.first.offset();
        }

        edge_.first.offset( saved_first_offset );       // restore universe
        CTTL_TRACE_RESULT( false, '&' );
        return UniverseT::string_T::npos;
    }

};  // xtl_opbinand

// Typedefs for metaphors support

typedef xtl_wrap< xtl_opbinplus< relaxed_bool_T, xtl_wrap< xtl_opunarbang< xtl_wrap< xtl_position_eof > > > > >
universe_T;

}   // namespace cttl_impl

#endif // _CTTL_XTL_OP_IMPL_H_INCLUDED_

---