extended_reg_exp.h

/***************************************************************************
 *   Copyright (C) 2006 by Radko Mihal                                     *
 *   rmihal@pobox.sk                                                       *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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 General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.              *
 ***************************************************************************/
#ifndef EXTENDED_REGULAR_EXPRESSIONEXTENDED_REG_EXP_H
#define EXTENDED_REGULAR_EXPRESSIONEXTENDED_REG_EXP_H

namespace extended_regular_expression {

template<typename E>
class extended_reg_exp : public ere_base<E>
{
typedef typename grammar_to_parser::basic_parser<E>::parser_list 
                                                                                                                        parser_list;
        
        class ere_branch_or_extended_reg_exp : public ere_base<E>
        {
                grammar_to_parser::basic_choice<E, ere_branch<E> >      m_branch;
                grammar_to_parser::basic_terminal<E,'|'>                        m_or;
                grammar_to_parser::basic_choice<E, extended_reg_exp<E> >        
                                                                                                                        m_ext_regexp;
        public:
                ere_branch_or_extended_reg_exp() : ere_base<E>() {};
                ~ere_branch_or_extended_reg_exp() {};
                
                unsigned long recognize( const E* buf, 
                                                                const unsigned long buf_length,
                                                                const unsigned long buf_offset,
                                                                bool try_positions = true );
                void assign_matches( matches::match_key parent_address, 
                                                        unsigned long& branch_pos, 
                                                        matches& m );
                void push_parsers( parser_list& l );
        };
        
        grammar_to_parser::basic_choice<E, ere_branch<E> >      m_branch;
        grammar_to_parser::basic_non_terminal<E, ere_branch_or_extended_reg_exp >
                                                                                                                m_branch_or_ext_regexp;
        
public:
    
        extended_reg_exp() : 
                ere_base<E>(), 
                m_branch_or_ext_regexp() {};
        ~extended_reg_exp() {};

        unsigned long recognize( const E* buf, 
                                                        const unsigned long buf_length,
                                                        const unsigned long buf_offset,
                                                        bool try_positions = true  );
        void assign_matches( matches::match_key parent_address, 
                                                unsigned long& branch_pos, 
                                                matches& m );
        
        void push_parsers( parser_list& l );
};




template< typename E > 
unsigned long ere_expression<E>::subexpression::recognize( 
                                                                                                        const E* buf, 
                                                                                                        const unsigned long buf_length,
                                                                                                        const unsigned long buf_offset,
                                                                                                        bool try_positions )
{
        m_extened_regexp->recognize( buf, buf_length, buf_offset );
        m_is_rec = m_extened_regexp->is_recognized();
        if( m_is_rec )
        {
                m_rec_size = m_extened_regexp->recognize( buf, buf_length, buf_offset );
                m_rec_pos = m_extened_regexp->recognized_position();
        }
        return m_rec_size;
}

template< typename E > 
void ere_expression<E>::subexpression::assign_matches( 
                                                                                                        matches::match_key key, 
                                                                                                        unsigned long& branch_pos, 
                                                                                                        matches& m )
{
        key += '.';
        key += to_str(branch_pos);
        unsigned long new_branch_pos = 0;
        m_extened_regexp->assign_matches( key, branch_pos, m );
}


template< typename E > 
void ere_expression<E>::subexpression::push_parsers( parser_list& l )
{
        l.push_back( &m_left_paren );
        l.push_back( &m_extened_regexp );
        l.push_back( &m_right_paren );
}

template< typename E > 
unsigned long ere_expression<E>::ere_expression_and_dupl::divide_and_recognize(
                                                                                                const E* buf, 
                                                                                                const unsigned long buf_length,
                                                                                                const unsigned long buf_offset,
                                                                                                unsigned long rep,
                                                                                                bool assign_matches )
{
        m_is_rec = true;
        if( rep == m_dup->get_max() )
        {
                m_dup->set_recognized_dup(rep);
                return 0;
        }
        unsigned long best_left_side_buf_len = 0;
        unsigned long best_rec_size = 0;
        unsigned long left_side_buf_len = buf_length;
        unsigned long left_rec_size = 0;
        while( m_is_rec )
        {
                m_ere->recognize( buf, left_side_buf_len, buf_offset, true );
                if( m_ere->is_recognized() )
                {
                        left_rec_size = m_ere->recognized_size();
                        // m_ere->recognized_position() is always same as buf_offset
                        m_rec_size = divide_and_recognize( 
                                                                buf, 
                                                                buf_length, 
                                                                buf_offset + left_rec_size,
                                                                rep+1,
                                                                false );
                        if( m_is_rec )
                        {
                                // previous method succeeded
                                if( best_rec_size < m_rec_size + left_rec_size )
                                {
                                        best_rec_size = m_rec_size + left_rec_size;
                                        best_left_side_buf_len = left_side_buf_len;
                                }       
                        }
                        left_side_buf_len = buf_offset + left_rec_size - 1;
                        m_is_rec = true;
                }
                else
                {
                        m_is_rec = false;
                }
        }
        
        if( best_rec_size > 0 )
        {
                if( assign_matches )
                {
                        m_ere->recognize( buf, best_left_side_buf_len, buf_offset, true );
                        unsigned long branch_pos = rep;
                        m_ere->assign_matches( "", branch_pos, m_matches );
                        
                        m_rec_size = 0;
                        left_rec_size = m_ere->recognized_size();
                        divide_and_recognize( 
                                                                buf, 
                                                                buf_length, 
                                                                buf_offset + left_rec_size,
                                                                rep+1,
                                                                true );
                        m_rec_size += left_rec_size;
                }
                else
                {
                        m_is_rec = true;
                        m_rec_size = best_rec_size;
                }
        }
        else if( rep >= m_dup->get_min() ) // the ere was recognized for no buf_length
        {
                m_rec_size = 0;
                m_is_rec = true;
        }
        else
        {
                m_is_rec = false;
        }
        return m_rec_size;      
}


template< typename E > 
unsigned long ere_expression<E>::ere_expression_and_dupl::recognize( 
                                                                                                const E* buf,
                                                                                                const unsigned long buf_length, 
                                                                                                const unsigned long buf_offset,
                                                                                                bool try_positions )
{
        unsigned long rep = 1;
        
        if( m_ere->is_subexpression() )
        {
                m_matches.clear();
                // different handling for subexpressions - need to try different 
                // splits on buffer, so expressions like ((ab){1,3}){5} match the 
                // input like "ababababab"
                // --- recursive calls
                divide_and_recognize( buf, 
                                                                buf_length,
                                                                buf_offset,
                                                                0,
                                                                true );
                m_rec_pos = buf_offset;
                return m_rec_size;
        }
        
        // else the ere is not subexpression - can be made faster then
        m_ere->recognize( buf, buf_length, buf_offset, try_positions );
        m_is_rec = m_ere->is_recognized();
        m_rec_pos = m_ere->recognized_position();
        m_rec_size = m_ere->recognized_size();
        
        if( m_ere->is_recognized() && m_ere->is_subexpression() )
        {
                unsigned long branch_pos = 0;
                m_ere->assign_matches( "", branch_pos, m_matches );
        }
        
        while( m_is_rec && rep < m_dup->get_max() )
        {
                m_ere->recognize( buf, 
                                                buf_length,
                                                m_rec_pos+m_rec_size,
                                                false ); // don't try next positions
                if( m_ere->is_recognized() )
                {
                        m_rec_size += m_ere->recognized_size();
                        rep++;
                }
                else if( rep < m_dup->get_min() )
                {
                        m_is_rec = false;
                        m_rec_pos = 0;
                        m_rec_size = 0;
                        m_matches.clear(); // negative return
                }
                else
                {
                        break; // positive return
                }
        }
        m_dup->set_recognized_dup( rep );
        return m_rec_size;      
}

template< typename E > 
void ere_expression<E>::ere_expression_and_dupl::assign_matches( 
                                                                                                        matches::match_key key, 
                                                                                                        unsigned long& branch_pos, 
                                                                                                        matches& m )
{
        if( m_ere->is_subexpression() )
        {
                // in this case matches are in private collection, don't need 
                // to assign in loop
                m.extend( key, m_matches );
        }
        else 
        {
                for( int i = 0; i < m_dup->get_recognized_dup(); i++ )
                {
                        m_ere->assign_matches( key, branch_pos, m );
                }
        }
}

template< typename E > 
void ere_expression<E>::ere_expression_and_dupl::push_parsers( parser_list& l )
{
        l.push_back( &m_ere );
        l.push_back( &m_dup );
}

template<typename E>
unsigned long ere_expression<E>::recognize(const E* buf, 
                                                                                const unsigned long buf_length, 
                                                                                const unsigned long buf_offset,
                                                                                bool try_positions)     
{
        m_is_rec = false;
        m_rec_pos = buf_offset;
        m_rec_size = 0;
        
        if( m_one_elem.is_parsed() )
        {
                while( !m_is_rec && m_rec_pos < buf_length )
                {
                        m_rec_size = m_one_elem->recognize( buf, buf_length, m_rec_pos );
                        m_is_rec = m_rec_size > 0;
                        if( m_is_rec )
                        {
                                // m_rec_size = m_one_elem->recognized_size();
                        }
                        else if( try_positions )
                        {
                                m_rec_pos++;
                        }
                        else
                        {
                                break;
                        }
                }
        }
        else if( m_left_anchor.is_parsed() || m_right_anchor.is_parsed() )
        {
                m_is_rec = true;
        } 
        else if( m_ere_expr_and_dup.is_parsed() )
        {
                m_ere_expr_and_dup->recognize( buf, buf_length, buf_offset, try_positions );
                m_is_rec = m_ere_expr_and_dup->is_recognized() ;
                if( m_is_rec )
                {
                        m_rec_pos = m_ere_expr_and_dup->recognized_position();
                        m_rec_size = m_ere_expr_and_dup->recognized_size();
                }
        }
        else
        {
                m_subexpression->recognize( buf, buf_length, buf_offset );
                m_is_rec = m_subexpression->is_recognized();
                m_rec_size = m_subexpression->recognized_size() + 
                                        m_subexpression->recognized_position() -
                                        buf_offset;
        }
        return m_rec_size;
}

template<typename E>
void ere_expression<E>::assign_matches( matches::match_key key, 
                                                                                unsigned long& branch_pos, 
                                                                                matches& m )
{
        if( m_subexpression.is_parsed() )
        {
                branch_pos++;
                m_subexpression->assign_matches( key, branch_pos, m );
        } 
        else if( m_ere_expr_and_dup.is_parsed() )
        {
                m_ere_expr_and_dup->assign_matches( key, branch_pos, m );
        }
}

template<typename E>
void ere_expression<E>::push_parsers( parser_list& l )
{
        l.push_back( &m_ere_expr_and_dup );
        l.push_back( &m_one_elem );
        l.push_back( &m_left_anchor );
        l.push_back( &m_right_anchor );
        l.push_back( &m_subexpression );
}

template<typename E>
unsigned long ere_branch<E>::ere_expression_ere_branch::recognize( 
                                                                                                const E* buf, 
                                                                                                const unsigned long buf_length,
                                                                                                const unsigned long buf_offset,
                                                                                                bool try_positions )
{
        m_is_rec = false;
        m_rec_pos = 0;
        m_rec_size = 0;
        if( m_ere_branch->is_right_anchor() )
        {
                // different processing for this kind of expression - no splitting retries
                m_ere_expression->recognize( buf, buf_length, buf_offset );
                if( m_ere_expression->is_recognized() )
                {
                        m_rec_size = m_ere_expression->recognized_size();
                        m_rec_pos = m_ere_expression->recognized_position();
                        m_is_rec = ((m_rec_pos + m_rec_size) == buf_length);
                        if( !m_is_rec )
                        {
                                m_rec_pos = 0;
                                m_rec_size = 0;
                        }
                }
                return m_rec_size;
        }
        
        if( m_ere_expression->is_left_anchor() )
        {
                m_ere_branch->recognize( buf, buf_length, buf_offset, true );
                m_is_rec = m_ere_branch->is_recognized() &&
                                        (m_ere_branch->recognized_position() == buf_offset);
                if( m_is_rec )
                {
                        m_rec_pos = buf_offset;
                        m_rec_size = m_ere_branch->recognized_size();
                }
                return m_rec_size;
        }

        
        unsigned long buf_split = 0;
        unsigned long longest_recognized_size = 0;
        unsigned long buf_split_for_shortest_size = 0;
        unsigned long shortest_left_recognized_size = INT_MAX;
        unsigned long buf_split_for_longest_size = buf_split;
        bool left_side_recognized = true;
        m_is_rec = true;

        // try all possible splits - this downsizes performance, but is necessary to 
        // recognize expressions like (wee|week)(knights|night)  - for input 
        // 'weeknights' must recognize all 10 characters
        while( left_side_recognized && buf_split < buf_length - buf_offset )
        {
                m_ere_expression->recognize( buf, buf_length-buf_split, buf_offset );
                left_side_recognized = m_ere_expression->is_recognized();
                if( left_side_recognized )
                {
                        m_rec_size = m_ere_expression->recognized_size();
                        m_rec_pos = m_ere_expression->recognized_position();

                        // try the right side
                        m_ere_branch->recognize( 
                                                        buf,
                                                        buf_length,
                                                        m_rec_pos + m_rec_size,
                                                        false ); // the 'false' says that trying next 
                                                                        // positions is not required
                        m_is_rec = m_ere_branch->is_recognized();
                        if( m_is_rec )
                        {
                                buf_split = buf_length - m_rec_pos - m_rec_size;
                                if( shortest_left_recognized_size > m_rec_size )
                                 // compared with ere_expression->recognized_size()
                                {
                                        // use if ereexpressino is 'lazy' (which seems strange in this alg.)
                                        shortest_left_recognized_size = m_rec_size;
                                        buf_split_for_shortest_size = buf_split;
                                }
                                        
                                m_rec_size += m_ere_branch->recognized_size();
                                if( longest_recognized_size < m_rec_size )
                                {
                                        buf_split_for_longest_size = buf_split;
                                        longest_recognized_size = m_rec_size;
                                }
                        }
                        // try more narrow split for left side
                        buf_split++;
                }                       
        }
        // now once again for found best split - here I feel possible 
        // performance improvement - TODO if there were no recognitions after the 
        // best one, don't need to recognize again
        if( longest_recognized_size > 0 || shortest_left_recognized_size < INT_MAX )
        {
                if( m_ere_expression->is_lazy() )
                {
                        m_ere_expression->recognize( buf, 
                                                                                buf_length-buf_split_for_shortest_size, 
                                                                                buf_offset );
                }
                else
                {
                        // greedy
                        m_ere_expression->recognize( buf, 
                                                                                buf_length-buf_split_for_longest_size, 
                                                                                buf_offset );
                }
                m_rec_size = m_ere_expression->recognized_size();
                m_rec_pos = m_ere_expression->recognized_position();
                
                // try the right side
                m_ere_branch->recognize( 
                                                buf,
                                                buf_length,
                                                m_rec_pos + m_rec_size,
                                                false ); // the 'false' says that trying next 
                                                                // positions is not required
                m_rec_size += m_ere_branch->recognized_size();
                m_is_rec = true;
                
        }
        else
        {
                m_is_rec = false;
        }
        return m_rec_size;
}       

template<typename E>
void ere_branch<E>::ere_expression_ere_branch::assign_matches( 
                                                                                matches::match_key parent_address, 
                                                                                unsigned long& branch_pos, 
                                                                                matches& m )
{
        if( m_ere_branch.is_parsed() && m_ere_expression.is_parsed() )
        {
                m_ere_expression->assign_matches( parent_address, branch_pos, m );
                m_ere_branch->assign_matches( parent_address, branch_pos, m );
        }
}

template<typename E>
void ere_branch<E>::ere_expression_ere_branch::push_parsers( parser_list& l )
{
        l.push_back( &m_ere_expression );
        l.push_back( &m_ere_branch );
}

template<typename E>
unsigned long ere_branch<E>::recognize( const E* buf, 
                                                                                const unsigned long buf_length, 
                                                                                const unsigned long buf_offset,
                                                                                bool try_positions )
{
        if( m_ere.is_parsed() )
        {
                m_ere->recognize( buf, buf_length, buf_offset, try_positions );
                m_is_rec = m_ere->is_recognized();
                m_rec_pos = m_ere->recognized_position();
                m_rec_size = m_ere->recognized_size();
        }
        else
        {
                m_ere_expression_ere_branch->recognize( buf, buf_length, buf_offset, try_positions );
                m_is_rec = m_ere_expression_ere_branch->is_recognized();
                m_rec_pos = m_ere_expression_ere_branch->recognized_position();
                m_rec_size = m_ere_expression_ere_branch->recognized_size();
        }                       
        return m_rec_size;
}

template<typename E>
void ere_branch<E>::assign_matches( matches::match_key parent_address, 
                                                                        unsigned long& branch_pos, 
                                                                        matches& m )
{
        if( m_ere.is_parsed() )
        {
                m_ere->assign_matches( parent_address, branch_pos, m );
        }
        else
        {
                m_ere_expression_ere_branch->assign_matches( parent_address, branch_pos, m );
        }
}

template<typename E>
void ere_branch<E>::push_parsers( parser_list& l )
{
        l.push_back( &m_ere_expression_ere_branch );
        l.push_back( &m_ere );
}

template<typename E>
unsigned long extended_reg_exp<E>::ere_branch_or_extended_reg_exp::recognize( 
                                                                                                        const E* buf, 
                                                                                                        const unsigned long buf_length,
                                                                                                        const unsigned long buf_offset,
                                                                                                        bool try_positions )
{
        m_rec_size = 0;
        m_rec_pos = 0;
        m_ext_regexp->recognize( buf, buf_length, buf_offset );
        m_branch->recognize( buf, buf_length, buf_offset );
        // check whichone is better match
        if( m_ext_regexp->is_recognized() && m_branch->is_recognized() )
        {
                if( m_branch->recognized_size() > m_ext_regexp->recognized_size() )
                {
                        m_ext_regexp->unset();
                }
                else
                {
                        m_branch->unset();
                }
        }
        
        m_is_rec = true;
        if( m_ext_regexp->is_recognized() )
        {
                m_rec_pos = m_ext_regexp->recognized_position();
                m_rec_size = m_ext_regexp->recognized_size();
        }
        else if( m_branch->is_recognized() )
        {
                m_rec_pos = m_branch->recognized_position();
                m_rec_size = m_branch->recognized_size();
        }
        else
        {
                m_is_rec = false;
        }
        return m_rec_size;
}

template<typename E>
void extended_reg_exp<E>::ere_branch_or_extended_reg_exp::assign_matches( 
                                                                                matches::match_key parent_address, 
                                                                                unsigned long& branch_pos, 
                                                                                matches& m )
{
        if( m_branch->is_recognized() )
        {
                m_branch->assign_matches( parent_address, branch_pos, m );
        }
        else
        {
                m_ext_regexp->assign_matches( parent_address, branch_pos, m );
        }
}

template<typename E>
void extended_reg_exp<E>::ere_branch_or_extended_reg_exp::push_parsers( 
                                                                                                                        parser_list& l )
{
        l.push_back( &m_branch );
        l.push_back( &m_or );
        l.push_back( &m_ext_regexp );
}

template<typename E>
unsigned long extended_reg_exp<E>::recognize( const E* buf, 
                                                                                        const unsigned long buf_length,
                                                                                        const unsigned long buf_offset,
                                                                                        bool try_positions )
{
        m_rec_pos = 0;
        m_rec_size = 0;
        if( m_branch.is_parsed() )
        {
                m_branch->recognize( buf, buf_length, buf_offset );
                m_is_rec = m_branch->is_recognized();
                if( m_is_rec )
                {
                        m_rec_pos = m_branch->recognized_position();
                        m_rec_size = m_branch->recognized_size();
                }
        }
        else
        {
                m_branch_or_ext_regexp->recognize( buf, buf_length, buf_offset );
                m_is_rec = m_branch_or_ext_regexp->is_recognized();
                if( m_is_rec )
                {
                        m_rec_pos = m_branch_or_ext_regexp->recognized_position();
                        m_rec_size = m_branch_or_ext_regexp->recognized_size();
                }
        }
        return m_rec_size;
}

template<typename E>
void extended_reg_exp<E>::assign_matches( matches::match_key key, 
                                                                                unsigned long& branch_pos, 
                                                                                matches& m )
{
        m.insert( key, match( m_rec_pos, m_rec_size ) );
        unsigned long new_branch_pos = 0;
        if( m_branch.is_parsed() )
        {
                m_branch->assign_matches( key, new_branch_pos, m );
        }
        else
        {
                m_branch_or_ext_regexp->assign_matches( key, new_branch_pos, m );
        }
}

template<typename E>
void extended_reg_exp<E>::push_parsers( parser_list& l )
{
        l.push_back( &m_branch_or_ext_regexp );
        l.push_back( &m_branch );
}

};

#endif

---