RegExpOptimize.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
#include <ext/iterator>
 
#include <regexp/unbounded/UnboundedRegExp.h>
#include <regexp/unbounded/UnboundedRegExpElements.h>
 
#include <regexp/formal/FormalRegExp.h>
#include <regexp/formal/FormalRegExpElements.h>
 
#include <regexp/properties/RegExpEpsilon.h>
#include <exception/CommonException.h>
 
namespace regexp {
 
namespace simplify {
 
/*
 * Optimizes RegExp (or its subtree) using axioms defined in Melichar 2.87
 * (A1 to A10) and Melichar 2.95(V1 through V6 and V8, V9, V10)
 * All methods return new tree.
 *
 * List of optimization on nodes:
 *  - RegExpAlternation: A1, A2, A3, A4, A9, V2, V5, V6
 *  - RegExpConcatenation: A5, A6, A7, A8, V8, V9
 *  - RegExpIteration: A10, V1, V3, V4, V10
 *
 * Details: ( id : direction of optim. : optim )
 *  - A1 : -> : x + ( y + z ) = ( x + y ) + z = x + y + z
 *  - A2 : <- : x + y = y + x
 *  - A3 : -> : x + \0 = x
 *  - A4 : -> : x + x = x
 *  - A5 : -> : x(yz) = (xy)z = xyz
 *  - A6 : -> : \ex = x\e = x
 *  - A7 : -> : \0x = x\0 = \0
 *  - A8 : <- : x( y + z ) = xy + xz
 *  - A9 : <- : ( x + y )z = xz + yz
 *  - A10: <- : x* = \e + x*x
 *  - A11: <- : x* = ( \e + x )*
 *  - V1 : -> : \0* = \e
 *  - V2 : -> : x* + x = x*
 *  - V3 : -> : x** = x*
 *  - V4 : <- : ( x + y )* = (x*y*)*
 *  - V5 : <- : x*y = y + x*xy
 *  - V6 : <- : x*y = y + xx*y
 *  - V7 :    : bleh
 *  - V8 : -> : if \e in h(x) => xx* = x*
 *  - V8R : -> : if \e in h(x) => x*x = x*
 *  - V9 : -> : (xy)*x = x(yx)*
 *  - V10: <- : ( x + y )* = ( x* + y* )*
 *
 *  - X1 : -> : a* + \e = a*
 */
class RegExpOptimize {
public:
 
    template < class SymbolType >
    static regexp::UnboundedRegExp < SymbolType > optimize( const regexp::UnboundedRegExp < SymbolType > & regexp );
 
    template < class SymbolType >
    static regexp::UnboundedRegExpStructure < SymbolType > optimize( const regexp::UnboundedRegExpStructure < SymbolType > & regexp );
 
    template < class SymbolType >
    static void optimize( regexp::UnboundedRegExpAlternation < SymbolType > & alt, bool recursive = true );
 
    template < class SymbolType >
    static void optimize( regexp::UnboundedRegExpConcatenation < SymbolType > & concat, bool recursive = true );
 
    template < class SymbolType >
    static void optimize( regexp::UnboundedRegExpIteration < SymbolType > & iter, bool recursive = true );
 
    template < class SymbolType >
    static regexp::FormalRegExp < SymbolType > optimize( const regexp::FormalRegExp < SymbolType > & regexp );
    template < class SymbolType >
    static regexp::FormalRegExpStructure < SymbolType > optimize( const regexp::FormalRegExpStructure < SymbolType > & regexp );
    template < class SymbolType >
    static void optimize( regexp::FormalRegExpElement < SymbolType > & element );
private:
    template < class SymbolType >
    class Unbounded {
    public:
        static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > visit ( regexp::UnboundedRegExpAlternation < SymbolType > && alt, bool recursive );
        static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > visit ( regexp::UnboundedRegExpConcatenation < SymbolType > && concat, bool recursive );
        static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > visit ( regexp::UnboundedRegExpIteration < SymbolType > && iter, bool recursive );
        static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > visit ( regexp::UnboundedRegExpSymbol < SymbolType > && node, bool recursive );
        static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > visit ( regexp::UnboundedRegExpEmpty < SymbolType > && node, bool recursive );
        static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > visit ( regexp::UnboundedRegExpEpsilon < SymbolType > && node, bool recursive );
 
        static bool A1( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool A2( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool A3( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool A4( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool A5( regexp::UnboundedRegExpConcatenation < SymbolType > & node );
        static bool A6( regexp::UnboundedRegExpConcatenation < SymbolType > & node );
        static bool A7( regexp::UnboundedRegExpConcatenation < SymbolType > & node );
        static bool A8( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool A9( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool A10( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool A11( regexp::UnboundedRegExpIteration < SymbolType > & node );
        static bool V1( regexp::UnboundedRegExpIteration < SymbolType > & node );
        static bool V2( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool V3( regexp::UnboundedRegExpIteration < SymbolType > & node );
        static bool V4( regexp::UnboundedRegExpIteration < SymbolType > & node );
        static bool V5( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool V6( regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static bool V8( regexp::UnboundedRegExpConcatenation < SymbolType > & node );
        static bool V8R( regexp::UnboundedRegExpConcatenation < SymbolType > & node );
        static bool V9( regexp::UnboundedRegExpConcatenation < SymbolType > & node );
        static bool V10( regexp::UnboundedRegExpIteration < SymbolType > & node );
 
        static bool X1( regexp::UnboundedRegExpAlternation < SymbolType > & node );
    };
 
    template < class SymbolType >
    static ext::smart_ptr < regexp::FormalRegExpElement < SymbolType > > optimizeInner( const regexp::FormalRegExpElement < SymbolType > & node );
 
    template < class SymbolType >
    static bool S( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A1( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A2( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A3( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A4( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A5( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A6( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A7( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A8( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A9( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A10( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool A11( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool V1( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool V2( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool V3( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool V4( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool V5( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool V6( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool V8( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool V9( regexp::FormalRegExpElement < SymbolType > * & node );
    template < class SymbolType >
    static bool V10( regexp::FormalRegExpElement < SymbolType > * & node );
 
    template < class SymbolType >
    static bool X1( regexp::FormalRegExpElement < SymbolType > * & node );
};
 
template < class SymbolType >
FormalRegExp < SymbolType > RegExpOptimize::optimize( const FormalRegExp < SymbolType > & regexp ) {
    return regexp::FormalRegExp < SymbolType > ( RegExpOptimize::optimize ( regexp.getRegExp ( ) ) );
}
 
template < class SymbolType >
FormalRegExpStructure < SymbolType > RegExpOptimize::optimize( const FormalRegExpStructure < SymbolType > & regexp ) {
    ext::smart_ptr < FormalRegExpElement < SymbolType > > optimized = optimizeInner( regexp.getStructure ( ) );
 
    return regexp::FormalRegExpStructure < SymbolType > ( * optimized );
}
 
template < class SymbolType >
UnboundedRegExp < SymbolType > RegExpOptimize::optimize( const UnboundedRegExp < SymbolType > & regexp ) {
    return regexp::UnboundedRegExp < SymbolType > ( RegExpOptimize::optimize ( regexp.getRegExp ( ) ) );
}
 
template < class SymbolType >
UnboundedRegExpStructure < SymbolType > RegExpOptimize::optimize( const UnboundedRegExpStructure < SymbolType > & regexp ) {
    UnboundedRegExpStructure < SymbolType > structure = regexp;
 
    return regexp::UnboundedRegExpStructure < SymbolType > ( std::move ( structure.getStructure ( ) ).template accept < ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > >, RegExpOptimize::Unbounded < SymbolType > > ( true ) );
}
 
} /* namespace simplify */
 
} /* namespace regexp */
 
#include "RegExpOptimizeUnboundedPart.hpp"
#include "RegExpOptimizeFormalPart.hpp"