regexpr2.cpp
上传用户:dzyhzl
上传日期:2019-04-29
资源大小:56270k
文件大小:210k
源码类别:

模拟服务器

开发平台:

C/C++

  1. //+---------------------------------------------------------------------------
  2. //
  3. //  Copyright ( C ) Microsoft Corporation, 1994 - 2002.
  4. //
  5. //  File:       regexpr2.cpp
  6. //
  7. //  Contents:   implementation for rpattern methods, definitions for all the
  8. //              subexpression types used to perform the matching, the
  9. //              charset class definition .
  10. //
  11. //  Classes:    too many to list here
  12. //
  13. //  Functions:
  14. //
  15. //  Author:     Eric Niebler ( ericne@microsoft.com )
  16. //
  17. //  History:    12-11-1998   ericne   Created
  18. //              01-05-2001   ericne   Removed dependency on VC's choice
  19. //                                    of STL iterator types.
  20. //              08-15-2001   ericne   Removed regexpr class, moved match
  21. //                                    state to match_results container.
  22. //              09-17-2001   nathann  Add DEBUG_HEAP_SUPPORT
  23. //              11-16-2001   ericne   Add stack-conservative algorithm
  24. //
  25. //----------------------------------------------------------------------------
  26. #ifdef _MSC_VER
  27. // unlimited inline expansion ( compile with /Ob1 or /Ob2 )
  28. # pragma inline_recursion( on )
  29. # pragma inline_depth( 255 )
  30. // warning C4127: conditional expression is constant
  31. // warning C4355: 'this' : used in base member initializer list
  32. // warning C4702: unreachable code
  33. // warning C4710: function 'blah' not inlined
  34. // warning C4786: identifier was truncated to '255' characters in the debug information
  35. # pragma warning( disable : 4127 4355 4702 4710 4786 )
  36. #endif
  37. #include <cctype>
  38. #include <cwctype>
  39. #include <cassert>
  40. #include <malloc.h>
  41. #include <algorithm>
  42. #include <functional>
  43. #if defined( _MSC_VER ) & defined( _MT )
  44. # include <windows.h>
  45. #endif
  46. // If the implementation file has been included in the header, then we
  47. // need to mark some functions as inline to prevent them from being multiply
  48. // defined.  But if the implementation file is not included in the header,
  49. // we can't mark them as inline, otherwise the linker won't find them.
  50. #ifdef REGEXPR_H
  51. # define REGEXPR_H_INLINE inline
  52. #else
  53. # define REGEXPR_H_INLINE
  54. # include "regexpr2.h"
  55. #endif
  56. #ifndef alloca
  57. # define alloca _alloca
  58. #endif
  59. // Rather non-portable code below. The flags to the _isctype
  60. // CRT routine, and even the _isctype routine itself, are
  61. // not standard. This works for me on VC and on my linux box,
  62. // but it probably won't work for everyone.  :-(
  63. #ifndef _MSC_VER
  64. # define __assume( x ) assert( false ); return NULL;
  65. # define _UPPER   _ISupper
  66. # define _LOWER   _ISlower
  67. # define _ALPHA   _ISalpha
  68. # define _DIGIT   _ISdigit
  69. # define _HEX     _ISxdigit
  70. # define _SPACE   _ISspace
  71. # define _PRINT   _ISprint
  72. # define _GRAPH   _ISgraph
  73. # define _BLANK   _ISblank
  74. # define _CONTROL _IScntrl
  75. # define _PUNCT   _ISpunct
  76. # define _ALNUM   _ISalnum
  77. #else
  78. # define _ALNUM ( _UPPER|_LOWER|_DIGIT )
  79. # define _PRINT ( _BLANK|_PUNCT|_UPPER|_LOWER|_DIGIT )
  80. # define _GRAPH ( _PUNCT|_UPPER|_LOWER|_DIGIT )
  81. #endif
  82. namespace regex
  83. {
  84. namespace detail
  85. {
  86. // For portably assigning a bare ptr to an auto_ptr.
  87. // (don't use reset() because some STL implementations
  88. // don't support it.)
  89. template< typename T, typename U >
  90. inline void assign_auto_ptr( std::auto_ptr<T> & lhs, U * rhs )
  91. {
  92.     std::auto_ptr<T> temp( rhs );
  93.     lhs = temp;
  94. }
  95. // VC's STL member function adapters don't handle const member functions,
  96. // so explicitly handle that special case with const_mem_fun1_t
  97. template<class R, class Ty, class A>
  98. class const_mem_fun1_t : public std::binary_function<Ty const *, A, R>
  99. {
  100.     R ( Ty::*m_p )( A ) const;
  101. public:
  102.     explicit const_mem_fun1_t( R ( Ty::*p )( A ) const )
  103.         : m_p( p ) {}
  104.     R operator()( Ty const * p, A arg ) const
  105.     {
  106.         return ( p->*m_p )( arg );
  107.     }
  108. };
  109. template<class R, class Ty, class A>
  110. inline const_mem_fun1_t<R, Ty, A> mem_fun( R ( Ty::*p )( A ) const )
  111. {
  112.     return const_mem_fun1_t<R, Ty, A>( p );
  113. }
  114. // On some systems, isctype is implemented as a macro. I need
  115. // a function so that I can bind args and use it in algorithms.
  116. #ifdef _isctype
  117. # error _isctype is a macro. It needs to be a function.
  118. #endif
  119. #ifdef __isctype
  120.  inline int _isctype( int c, int type ) { return __isctype( c, type ); }
  121. #endif
  122. #if defined( _MSC_VER ) & defined( _MT )
  123. // Global critical section used to synchronize the creation of static const patterns
  124. class CRegExCritSect : private CRITICAL_SECTION
  125. {
  126.     friend struct CRegExLock;
  127.     CRegExCritSect( CRegExCritSect const & );
  128.     CRegExCritSect()  { InitializeCriticalSection( this ); }
  129.     void Enter()      { EnterCriticalSection( this ); }
  130.     void Leave()      { LeaveCriticalSection( this ); }
  131.     static CRegExCritSect & Instance()
  132.     {
  133.         static CRegExCritSect s_objRegExCritSect;
  134.         return s_objRegExCritSect;
  135.     }
  136. public:
  137.     ~CRegExCritSect() { DeleteCriticalSection( this ); }
  138. };
  139. REGEXPR_H_INLINE CRegExLock::CRegExLock()
  140. {
  141.     CRegExCritSect::Instance().Enter();
  142. }
  143. REGEXPR_H_INLINE CRegExLock::~CRegExLock()
  144. {
  145.     CRegExCritSect::Instance().Leave();
  146. }
  147. #endif
  148. template< typename II, typename CI >
  149. inline size_t parse_int( II & istr, CI iend, size_t const max_ = unsigned( -1 ) )
  150. {
  151.     typedef typename std::iterator_traits<II>::value_type CH;
  152.     size_t retval = 0;
  153.     while( iend != istr && REGEX_CHAR(CH,'0') <= *istr && REGEX_CHAR(CH,'9') >= *istr && max_ > retval )
  154.     {
  155.         retval *= 10;
  156.         retval += ( size_t )( *istr - REGEX_CHAR(CH,'0') );
  157.         ++istr;
  158.     }
  159.     if( max_ < retval )
  160.     {
  161.         retval /= 10;
  162.         --istr;
  163.     }
  164.     return retval;
  165. }
  166. // Here is the implementation for the regex_arena class.
  167. // It takes advantage of the fact that all subexpression objects
  168. // allocated during pattern compilation will be freed all at once.
  169. // The sub_expr, custom_charset and basic_rpattern classes all must
  170. // cooperate with this degenerate allocation scheme.  But it is fast
  171. // and effective.  My patterns compile 40% faster with it.  YMMV.
  172. // NathanN:
  173. // By defining the symbol REGEX_DEBUG_HEAP the allocator object
  174. // no longer sub allocates memory.  This enables heap checking tools like
  175. // AppVerifier & PageHeap to find errors like buffer overruns
  176. #ifndef REGEX_DEBUG_HEAP
  177. # if REGEX_DEBUG
  178. #  define REGEX_DEBUG_HEAP 1
  179. # else
  180. #  define REGEX_DEBUG_HEAP 0
  181. # endif
  182. #endif
  183. REGEXPR_H_INLINE size_t DEFAULT_BLOCK_SIZE()
  184. {
  185. #   if REGEX_DEBUG_HEAP
  186.     // put each allocation in its own block
  187.     return 1;
  188. #   else
  189.     // put multiple allocation in each block
  190.     return 352;
  191. #   endif
  192. }
  193. struct regex_arena::block
  194. {
  195.     block * m_pnext;
  196.     size_t m_offset;
  197.     enum { HEADER_SIZE = sizeof( block* ) + sizeof( size_t ) };
  198.     unsigned char m_data[ 1 ];
  199. };
  200. inline void regex_arena::_new_block( size_t size )
  201. {
  202.     size_t blocksize = (std::max)( m_default_size, size ) + block::HEADER_SIZE;
  203.     block * pnew = static_cast<block*>( ::operator new( blocksize ) );
  204.     pnew->m_offset = 0;
  205.     pnew->m_pnext  = m_pfirst;
  206.     m_pfirst = pnew;
  207. }
  208. REGEXPR_H_INLINE regex_arena::regex_arena( size_t default_size )
  209.     : m_pfirst( NULL ), m_default_size( default_size )
  210. {
  211. }
  212. REGEXPR_H_INLINE regex_arena::~regex_arena()
  213. {
  214.     deallocate();
  215. }
  216. REGEXPR_H_INLINE void regex_arena::deallocate()
  217. {
  218.     for( block * pnext; m_pfirst; m_pfirst = pnext )
  219.     {
  220.         pnext = m_pfirst->m_pnext;
  221.         ::operator delete( static_cast<void*>( m_pfirst ) );
  222.     }
  223. }
  224. struct not_pod
  225. {
  226.     virtual ~not_pod() {}
  227. };
  228. REGEXPR_H_INLINE void * regex_arena::allocate( size_t size )
  229. {
  230.     if( 0 == size )
  231.         size = 1;
  232.     if( NULL == m_pfirst || m_pfirst->m_offset + size > m_default_size )
  233.         _new_block( size );
  234.     void * pnew = m_pfirst->m_data + m_pfirst->m_offset;
  235.     // ensure returned pointers are always suitably aligned
  236.     m_pfirst->m_offset += ( ( size + alignof<not_pod>::value - 1 )
  237.                             & ~( alignof<not_pod>::value - 1 ) );
  238.     return pnew;
  239. }
  240. REGEXPR_H_INLINE size_t regex_arena::max_size() const
  241. {
  242.     return size_t( -1 );
  243. }
  244. REGEXPR_H_INLINE void regex_arena::swap( regex_arena & that )
  245. {
  246.     std::swap( m_pfirst, that.m_pfirst );
  247.     std::swap( m_default_size, that.m_default_size );
  248. }
  249. template< typename T >
  250. inline void regex_destroy( T * pt ) { pt; pt->~T(); }
  251. inline void regex_destroy( char * ) {}
  252. inline void regex_destroy( wchar_t * ) {}
  253. ////
  254. // regex_allocator is a proper STL allocator.  It is a thin
  255. // wrapper around the regex_arrena object.  Note that deallocate
  256. // does nothing.  Memory isn't freed until the arena object
  257. // gets destroyed.
  258. template< typename T >
  259. struct regex_allocator
  260. {
  261.     typedef size_t size_type;
  262.     typedef ptrdiff_t difference_type;
  263.     typedef T *pointer;
  264.     typedef T const *const_pointer;
  265.     typedef T & reference;
  266.     typedef T const & const_reference;
  267.     typedef T value_type;
  268.     regex_allocator( regex_arena & arena )
  269.         : m_arena( arena ) { align_check(); }
  270. #if !defined(_MSC_VER) | _MSC_VER >= 1300
  271.     regex_allocator( regex_allocator const & alloc )
  272.         : m_arena( alloc.m_arena ) { align_check(); }
  273. #endif
  274.     template< typename U >
  275.     regex_allocator( regex_allocator<U> const & alloc )
  276.         : m_arena( alloc.m_arena ) { align_check(); }
  277.     pointer address( reference x ) const
  278.         {return &x;}
  279.     const_pointer address( const_reference x ) const
  280.         {return &x;}
  281.     pointer allocate( size_type size, void const * =0 )
  282.         {return static_cast<pointer>( m_arena.allocate( size * sizeof( T ) ) ); }
  283.     char *_Charalloc( size_type size )
  284.         {return static_cast<char*>( m_arena.allocate( size ) ); }
  285.     void deallocate( void *, size_type )
  286.         {}
  287.     void construct( pointer p, T const & t )
  288.         {new( ( void* )p ) T( t );}
  289.     void destroy( pointer p )
  290.         {regex_destroy( p );}
  291.     size_t max_size() const
  292.         {size_t size = m_arena.max_size() / sizeof( T );
  293.          return ( 0 < size ? size : 1 );}
  294.     template< typename U > struct rebind
  295.         {typedef regex_allocator<U> other;};
  296.     // BUGBUG after rpattern::swap, all regex_allocator
  297.     // objects refer to the wrong arena.
  298.     regex_arena & m_arena;
  299. private:
  300.     regex_allocator & operator=( regex_allocator const & );
  301.     static void align_check()
  302.     {
  303.         // The regex_arena uses not_pod to align memory. Use a compile-time
  304.         // assertion to make sure that T does not have worse alignment than not_pod.
  305.         static_assert<( ( size_t ) alignof<T>::value <= ( size_t ) alignof<not_pod>::value )> const align_check;
  306.         ( void ) align_check;
  307.     }
  308. };
  309. template< typename T, typename U >
  310. inline bool operator==( regex_allocator<T> const & rhs, regex_allocator<U> const & lhs )
  311.     {return &rhs.m_arena == &lhs.m_arena;}
  312. template< typename T, typename U >
  313. inline bool operator!=( regex_allocator<T> const & rhs, regex_allocator<U> const & lhs )
  314.     {return &rhs.m_arena != &lhs.m_arena;}
  315. // Use the regex allocator by default because it makes pattern compilation
  316. // and clean-up go much faster. If you define REGEX_NO_ALLOCATOR, though,
  317. // you can save some code bloat.
  318. // BUGBUG This is actually implementation-dependent. regex_allocator is
  319. // not a 100% compliant STL allocator. It does not have a default c'tor, and
  320. // all regex_allocator<T> instances do not necessarily compare equal for
  321. // any type T. To be truly portable, I would need to write my own containers
  322. // that do not make any of these assumptions.  Sigh.  Alternatively, I could
  323. // just give up passing regex_allocators to STL containers by compiling with
  324. // REGEX_NO_ALLOCATOR defined, but this make compiling patterns slow.  :-(
  325. #ifndef REGEX_NO_ALLOCATOR
  326. # define REGEX_ALLOCATOR regex_allocator
  327. #else
  328. # define REGEX_ALLOCATOR std::allocator
  329. #endif
  330. #if defined(_MSC_VER) & _MSC_VER < 1300
  331. # ifndef REGEX_NO_ALLOCATOR
  332. #  define MAKE_ALLOCATOR(type,arena) regex_allocator<type>(arena)
  333. # else
  334. #  define MAKE_ALLOCATOR(type,arena) std::allocator<type>()
  335. # endif
  336. #else
  337. // Define an allocator factory that can create
  338. // an allocator from a regex_arena.
  339. template< typename AL >
  340. struct allocator_factory
  341. {
  342.     template< typename T >
  343.     static typename AL::template rebind<T>::other create( regex_arena & )
  344.     {
  345.         typedef typename AL::template rebind<T>::other other;
  346.         return other();
  347.     }
  348. };
  349. template<>
  350. struct allocator_factory< regex_allocator<char> >
  351. {
  352.     template< typename T >
  353.     static regex_allocator<T> create( regex_arena & arena )
  354.     {
  355.         return regex_allocator<T>( arena );
  356.     }
  357. };
  358. #define MAKE_ALLOCATOR(type,arena) allocator_factory<REGEX_ALLOCATOR<char> >::template create<type>( arena )
  359. #endif
  360. // This class is used to speed up character set matching by providing
  361. // a bitset that spans the ASCII range. std::bitset is not used because
  362. // the range-checking slows it down.
  363. // Note: The division and modulus operations are optimized by the compiler
  364. // into bit-shift operations.
  365. class ascii_bitvector
  366. {
  367.     typedef unsigned int elem_type;
  368.     enum { CBELEM = CHAR_BIT * sizeof( elem_type ), // count of bits per element
  369.            CELEMS = ( UCHAR_MAX+1 ) / CBELEM };       // number of element in array
  370.     elem_type m_rg[ CELEMS ];
  371.     // Used to inline operations like: bv1 |= ~bv2; without creating temp bit vectors.
  372.     struct not_ascii_bitvector
  373.     {
  374.         ascii_bitvector const & m_ref;
  375.         not_ascii_bitvector( ascii_bitvector const & ref )
  376.             : m_ref( ref ) {}
  377.     private:
  378.         not_ascii_bitvector & operator=( not_ascii_bitvector const & );
  379.     };
  380. public:
  381.     ascii_bitvector()
  382.         { zero(); }
  383.     void zero()
  384.         { memset( m_rg, 0, CELEMS * sizeof( elem_type ) ); }
  385.     void set( unsigned char ch )
  386.         { m_rg[ ( ch / CBELEM ) ] |= ( ( elem_type )1U << ( ch % CBELEM ) ); }
  387.     bool operator[]( unsigned char ch ) const
  388.         { return 0 != ( m_rg[ ( ch / CBELEM ) ] & ( ( elem_type )1U << ( ch % CBELEM ) ) ); }
  389.     not_ascii_bitvector const operator~() const
  390.         { return not_ascii_bitvector( *this ); }
  391.     ascii_bitvector & operator|=( ascii_bitvector const & that )
  392.         { for( int i=0; i<CELEMS; ++i )
  393.               m_rg[ i ] |= that.m_rg[ i ];
  394.           return *this; }
  395.     ascii_bitvector & operator|=( not_ascii_bitvector const & that )
  396.         { for( int i=0; i<CELEMS; ++i )
  397.               m_rg[ i ] |= ~that.m_ref.m_rg[ i ];
  398.           return *this; }
  399.     ascii_bitvector & operator=( ascii_bitvector const & that )
  400.         { for( int i=0; i<CELEMS; ++i )
  401.               m_rg[ i ] = that.m_rg[ i ];
  402.           return *this; }
  403.     ascii_bitvector & operator=( not_ascii_bitvector const & that )
  404.         { for( int i=0; i<CELEMS; ++i )
  405.               m_rg[ i ] = ~that.m_ref.m_rg[ i ];
  406.           return *this; }
  407. };
  408. typedef std::pair<wchar_t, wchar_t> range_type;
  409. // determines if one range is less then another.
  410. // used in binary search of range vector
  411. struct range_less : public std::binary_function< range_type, range_type, bool >
  412. {
  413.     inline bool operator()( range_type const & rg1, range_type const & rg2 ) const
  414.     {
  415.         return rg1.second < rg2.first;
  416.     }
  417. };
  418. struct charset;
  419. template< typename A1, typename A2, typename A3 >
  420. struct charset_t
  421. {
  422.     bool                            m_fcompliment;
  423.     bool                            m_fskip_extended_check;
  424.     ascii_bitvector                 m_ascii_bitvector;
  425.     wctype_t                        m_posixcharson;
  426.     std::vector<range_type, A1>     m_range_vector;
  427.     std::list<wctype_t, A2>         m_posixcharsoff;
  428.     std::list<charset const *, A3>  m_nestedcharsets;
  429.     
  430.     charset_t( A1 const & a1 = A1(), A2 const & a2 = A2(), A3 const & a3 = A3() )
  431.         : m_fcompliment( false ),
  432.           m_fskip_extended_check( false ),
  433.           m_ascii_bitvector(),
  434.           m_posixcharson( 0 ),
  435.           m_range_vector( a1 ),
  436.           m_posixcharsoff( a2 ),
  437.           m_nestedcharsets( a3 )
  438.     {
  439.     }
  440.     // We'll be inheriting from this, so a virtual d'tor is regretably necessary.
  441.     virtual ~charset_t()
  442.     {
  443.     }
  444.     void clear()
  445.     {
  446.         m_fcompliment = false;
  447.         m_fskip_extended_check = false;
  448.         m_ascii_bitvector.zero();
  449.         m_posixcharson = 0;
  450.         m_range_vector.clear();
  451.         m_posixcharsoff.clear();
  452.         m_nestedcharsets.clear();
  453.     }
  454.     void add_range( range_type rg )
  455.     {
  456.         // Prevent excessive reallocs by reserving in blocks of 5
  457.         if( m_range_vector.capacity() == m_range_vector.size() )
  458.             m_range_vector.reserve( m_range_vector.size() + 5 );
  459.         m_range_vector.push_back( rg );
  460.     }
  461.     // merge one charset into another
  462.     charset_t & operator|=( charset const & that )
  463.     {
  464.         if( that.m_fcompliment )
  465.         {
  466.             // If no posix-style character sets are used, then we can merge this
  467.             // nested character set directly into the enclosing character set.
  468.             if( 0 == that.m_posixcharson     &&
  469.                 that.m_posixcharsoff.empty() &&
  470.                 that.m_nestedcharsets.empty() )
  471.             {
  472.                 m_ascii_bitvector |= ~ that.m_ascii_bitvector;
  473.                 // append the inverse of that.m_range_vector to this->m_range_vector
  474.                 wchar_t chlow = UCHAR_MAX;
  475.                 typedef std::vector<range_type>::const_iterator VCI;
  476.                 for( VCI prg = that.m_range_vector.begin(); prg != that.m_range_vector.end(); ++prg )
  477.                 {
  478.                     if( UCHAR_MAX + 1 != prg->first )
  479.                         add_range( range_type( wchar_t( chlow+1 ), wchar_t( prg->first-1 ) ) );
  480.                     chlow = prg->second;
  481.                 }
  482.                 if( WCHAR_MAX != chlow )
  483.                     add_range( range_type( wchar_t( chlow+1 ), WCHAR_MAX ) );
  484.             }
  485.             else
  486.             {
  487.                 // There is no simple way to merge this nested character
  488.                 // set into the enclosing character set, so we must save
  489.                 // a pointer to the nested character set in a list.
  490.                 m_nestedcharsets.push_back( & that );
  491.             }
  492.         }
  493.         else
  494.         {
  495.             m_ascii_bitvector |= that.m_ascii_bitvector;
  496.             m_range_vector.insert( m_range_vector.end(),
  497.                 that.m_range_vector.begin(),
  498.                 that.m_range_vector.end() );
  499.             m_posixcharson |= that.m_posixcharson;
  500.             std::copy( that.m_posixcharsoff.begin(),
  501.                        that.m_posixcharsoff.end() ,
  502.                        std::back_inserter( m_posixcharsoff ) );
  503.             std::copy( that.m_nestedcharsets.begin(),
  504.                        that.m_nestedcharsets.end(),
  505.                        std::back_inserter( m_nestedcharsets ) );
  506.         }
  507.         return *this;
  508.     }
  509.     // Note overloading based on second parameter
  510.     void set_bit( char ch, bool const fnocase )
  511.     {
  512.         if( fnocase )
  513.         {
  514.             m_ascii_bitvector.set( static_cast<unsigned char>( regex_tolower( ch ) ) );
  515.             m_ascii_bitvector.set( static_cast<unsigned char>( regex_toupper( ch ) ) );
  516.         }
  517.         else
  518.         {
  519.             m_ascii_bitvector.set( static_cast<unsigned char>( ch ) );
  520.         }
  521.     }
  522.     // Note overloading based on second parameter
  523.     void set_bit( wchar_t ch, bool const fnocase )
  524.     {
  525.         if( UCHAR_MAX >= ch )
  526.             set_bit( static_cast<char>( ch ), fnocase );
  527.         else
  528.             add_range( range_type( ch, ch ) );
  529.     }
  530.     // Note overloading based on second parameter
  531.     void set_bit_range( char ch1, char ch2, bool const fnocase )
  532.     {
  533.         if( static_cast<unsigned char>( ch1 ) > static_cast<unsigned char>( ch2 ) )
  534.             throw bad_regexpr( "invalid range specified in character set" );
  535.         if( fnocase )
  536.         {
  537.             // i is unsigned int to prevent overflow if ch2 is UCHAR_MAX
  538.             for( unsigned int i = static_cast<unsigned char>( ch1 ); 
  539.                  i <= static_cast<unsigned char>( ch2 ); ++i )
  540.             {
  541.                 m_ascii_bitvector.set( static_cast<unsigned char>( regex_toupper( (char)i ) ) );
  542.                 m_ascii_bitvector.set( static_cast<unsigned char>( regex_tolower( (char)i ) ) );
  543.             }
  544.         }
  545.         else
  546.         {
  547.             // i is unsigned int to prevent overflow if ch2 is UCHAR_MAX
  548.             for( unsigned int i = static_cast<unsigned char>( ch1 ); 
  549.                  i <= static_cast<unsigned char>( ch2 ); ++i )
  550.             {
  551.                 m_ascii_bitvector.set( static_cast<unsigned char>( i ) );
  552.             }
  553.         }
  554.     }
  555.     // Note overloading based on second parameter
  556.     void set_bit_range( wchar_t ch1, wchar_t ch2, bool const fnocase )
  557.     {
  558.         if( ch1 > ch2 )
  559.             throw bad_regexpr( "invalid range specified in character set" );
  560.         if( UCHAR_MAX >= ch1 )
  561.             set_bit_range( static_cast<char>( ch1 ), static_cast<char>( (std::min)( static_cast<wchar_t>( UCHAR_MAX ), ch2 ) ), fnocase );
  562.         if( UCHAR_MAX < ch2 )
  563.             add_range( range_type( (std::max)( static_cast<wchar_t>( UCHAR_MAX+1 ), ch1 ), ch2 ) );
  564.     }
  565.     void optimize( type2type<wchar_t> )
  566.     {
  567.         // this sorts on range_type.first ( uses operator<() for pair templates )
  568.         std::sort( m_range_vector.begin(), m_range_vector.end() );
  569.         // This merges ranges that overlap
  570.         for( size_t index = 1; index < m_range_vector.size(); )
  571.         {
  572.             if( m_range_vector[ index ].first <= m_range_vector[ index-1 ].second + 1 )
  573.             {
  574.                 m_range_vector[ index-1 ].second = (std::max)(
  575.                     m_range_vector[ index-1 ].second, m_range_vector[ index ].second );
  576.                 m_range_vector.erase( m_range_vector.begin() + index );
  577.             }
  578.             else
  579.                 ++index;
  580.         }
  581.         // For the ASCII range, merge the m_posixcharson info
  582.         // into the ascii_bitvector
  583.         if( m_posixcharson )
  584.         {
  585.             // BUGBUG this is kind of expensive. Think of a better way.
  586.             for( unsigned int i=0; i<=UCHAR_MAX; ++i )
  587.                 if( _isctype( i, m_posixcharson ) )
  588.                     m_ascii_bitvector.set( static_cast<unsigned char>( i ) );
  589.         }
  590.         // m_fskip_extended_check is a cache which tells us whether we
  591.         // need to check the m_posixcharsoff and m_nestedcharsets vectors,
  592.         // which would only be used in nested user-defined character sets
  593.         m_fskip_extended_check = m_posixcharsoff.empty() && m_nestedcharsets.empty();
  594.     }
  595.     void optimize( type2type<char> )
  596.     {
  597.         optimize( type2type<wchar_t>() );
  598.         // the posixcharson info was merged into the ascii bitvector,
  599.         // so we don't need to ever call _isctype ever again.
  600.         m_posixcharson = 0;
  601.     }
  602. #define DECLARE_EXTENDED_CHECK(FUN,CHAR,CTYPE,PMF)
  603.     bool FUN( CHAR ch ) const
  604.     {
  605.         if( m_fskip_extended_check )
  606.         {
  607.             assert( m_posixcharsoff.empty() && m_nestedcharsets.empty() );
  608.             return false;
  609.         }
  610.         return ( m_posixcharsoff.end() !=
  611.                  std::find_if( m_posixcharsoff.begin(), m_posixcharsoff.end(),
  612.                                std::not1( std::bind1st( std::ptr_fun( CTYPE ), ch ) ) ) )
  613.             || ( m_nestedcharsets.end() !=
  614.                  std::find_if( m_nestedcharsets.begin(), m_nestedcharsets.end(),
  615.                                std::bind2nd( regex::detail::mem_fun( PMF ), ch ) ) );
  616.     }
  617.     DECLARE_EXTENDED_CHECK(extended_check_narrow,char,_isctype,&charset::in_narrow)
  618.     DECLARE_EXTENDED_CHECK(extended_check_wide_with_case,wchar_t,iswctype,&charset::in_wide_with_case)
  619.     DECLARE_EXTENDED_CHECK(extended_check_wide_no_case,wchar_t,iswctype,&charset::in_wide_no_case)
  620. #undef DECLARE_EXTENDED_CHECK
  621.     // Note overloading based on parameter
  622.     bool in_narrow( char ch ) const
  623.     {
  624.         // Whoops, forgot to call optimize() on this charset
  625.         assert( 0 == m_posixcharson );
  626.         return m_fcompliment !=
  627.                (
  628.                     ( m_ascii_bitvector[ static_cast<unsigned char>( ch ) ] )
  629.                  || ( extended_check_narrow( ch ) )
  630.                );
  631.     }
  632.     inline bool in_range_vector_with_case( wchar_t ch ) const
  633.     {
  634.         return std::binary_search( m_range_vector.begin(), m_range_vector.end(),
  635.             range_type( ch, ch ), range_less() );
  636.     }
  637.     inline bool in_range_vector_no_case( wchar_t ch ) const
  638.     {
  639.         wchar_t const chup = regex_toupper( ch );
  640.         if( std::binary_search( m_range_vector.begin(), m_range_vector.end(),
  641.                 range_type( chup, chup ), range_less() ) )
  642.             return true;
  643.         wchar_t const chlo = regex_tolower( ch );
  644.         if( chup != chlo &&
  645.             std::binary_search( m_range_vector.begin(), m_range_vector.end(),
  646.                 range_type( chlo, chlo ), range_less() ) )
  647.             return true;
  648.         return false;
  649.     }
  650.     // Note overloading based on parameter
  651.     bool in_wide_with_case( wchar_t ch ) const
  652.     {
  653.         // use range_match_type to see if this character is within one of the
  654.         // ranges stored in m_rgranges.
  655.         return m_fcompliment !=
  656.                (
  657.                     ( ( UCHAR_MAX >= ch ) ?
  658.                       ( m_ascii_bitvector[ static_cast<unsigned char>( ch ) ] ) :
  659.                       (    ( ! m_range_vector.empty() && in_range_vector_with_case( ch ) )
  660.                         || ( m_posixcharson && iswctype( ch, m_posixcharson ) ) ) )
  661.                  || ( extended_check_wide_with_case( ch ) )
  662.                );
  663.     }
  664.     // Note overloading based on parameter
  665.     bool in_wide_no_case( wchar_t ch ) const
  666.     {
  667.         // use range_match_type to see if this character is within one of the
  668.         // ranges stored in m_rgranges.
  669.         return m_fcompliment !=
  670.                (
  671.                     ( ( UCHAR_MAX >= ch ) ?
  672.                       ( m_ascii_bitvector[ static_cast<unsigned char>( ch ) ] ) :
  673.                       (    ( ! m_range_vector.empty() && in_range_vector_no_case( ch ) )
  674.                         || ( m_posixcharson && iswctype( ch, m_posixcharson ) ) ) )
  675.                  || ( extended_check_wide_no_case( ch ) )
  676.                );
  677.     }
  678.     bool in( char ch, true_t ) const
  679.     {
  680.         return in_narrow( ch );
  681.     }
  682.     bool in( char ch, false_t ) const
  683.     {
  684.         return in_narrow( ch );
  685.     }
  686.     bool in( wchar_t ch, true_t ) const
  687.     {
  688.         return in_wide_with_case( ch );
  689.     }
  690.     bool in( wchar_t ch, false_t ) const
  691.     {
  692.         return in_wide_no_case( ch );
  693.     }
  694. private:
  695.     charset_t & operator=( charset_t const & that );
  696.     charset_t( charset_t const & that );
  697. };
  698. // Intrinsic character sets are allocated on the heap with the standard allocator.
  699. // They are either the built-in character sets, or the user-defined ones.
  700. struct charset : public charset_t< std::allocator<range_type>,
  701.                                    std::allocator<wctype_t>,
  702.                                    std::allocator<charset const *> >
  703. {
  704.     charset()
  705.     {
  706.     }
  707. private:
  708.     charset( charset const & );
  709.     charset & operator=( charset const & );
  710. };
  711. // charset is no longer an incomplete type so we now
  712. // know how to destroy one. free_charset() is used in syntax2.h
  713. REGEXPR_H_INLINE void free_charset( charset const * pcharset )
  714. {
  715.     delete pcharset;
  716. }
  717. // Custom character sets are the ones that appear in patterns between
  718. // square brackets.  They are allocated in a regex_arena to speed up
  719. // pattern compilation and to make rpattern clean-up faster.
  720. struct custom_charset : public charset_t< REGEX_ALLOCATOR< range_type >,
  721.                                           REGEX_ALLOCATOR< wctype_t >,
  722.                                           REGEX_ALLOCATOR< charset const * > >
  723. {
  724.     typedef REGEX_ALLOCATOR< range_type > A1;
  725.     typedef REGEX_ALLOCATOR< wctype_t > A2;
  726.     typedef REGEX_ALLOCATOR< charset const * > A3;
  727.     static void * operator new( size_t size, regex_arena & arena )
  728.     {
  729.         return arena.allocate( size );
  730.     }
  731.     static void operator delete( void *, regex_arena & ) {}
  732.     static void operator delete( void * ) {}
  733.     custom_charset( regex_arena & arena )
  734.         : charset_t<A1, A2, A3>( MAKE_ALLOCATOR(range_type,arena),
  735.                                  MAKE_ALLOCATOR(wctype_t,arena),
  736.                                  MAKE_ALLOCATOR(charset const*,arena) )
  737.     {
  738.     }
  739. private:
  740.     custom_charset( custom_charset const & );
  741.     custom_charset & operator=( custom_charset const & );
  742. };
  743. template< typename CH >
  744. class intrinsic_charsets
  745. {
  746.     struct intrinsic_charset : public charset
  747.     {
  748.         intrinsic_charset( bool fcompliment, wctype_t desc, char const * sz )
  749.         {
  750.             reset( fcompliment, desc, sz );
  751.         }
  752.         void reset( bool fcompliment, wctype_t desc, char const * sz )
  753.         {
  754.             clear();
  755.             m_fcompliment = fcompliment;
  756.             m_fskip_extended_check = true;
  757.             _set( desc, type2type<CH>() );
  758.             for( ; *sz; ++sz )
  759.                 m_ascii_bitvector.set( static_cast<unsigned char>( *sz ) );
  760.         }
  761.     protected:
  762.         void _set( wctype_t desc, type2type<char> )
  763.         {
  764.             m_ascii_bitvector.zero();
  765.             for( unsigned int i=0; i<=UCHAR_MAX; ++i )
  766.                 if( _isctype( i, desc ) )
  767.                     m_ascii_bitvector.set( static_cast<unsigned char>( i ) );
  768.         }
  769.         void _set( wctype_t desc, type2type<wchar_t> )
  770.         {
  771.             _set( desc, type2type<char>() );
  772.             m_posixcharson = desc;
  773.         }
  774.     private:
  775.         intrinsic_charset( intrinsic_charset const & );
  776.         intrinsic_charset & operator=( intrinsic_charset const & );
  777.     };
  778.     static intrinsic_charset & _get_word_charset()
  779.     {
  780.         static intrinsic_charset s_word_charset( false, _ALPHA|_DIGIT, "_" );
  781.         return s_word_charset;
  782.     }
  783.     static intrinsic_charset & _get_digit_charset()
  784.     {
  785.         static intrinsic_charset s_digit_charset( false, _DIGIT, "" );
  786.         return s_digit_charset;
  787.     }
  788.     static intrinsic_charset & _get_space_charset()
  789.     {
  790.         static intrinsic_charset s_space_charset( false, _SPACE, "" );
  791.         return s_space_charset;
  792.     }
  793.     static intrinsic_charset & _get_not_word_charset()
  794.     {
  795.         static intrinsic_charset s_not_word_charset( true, _ALPHA|_DIGIT, "_" );
  796.         return s_not_word_charset;
  797.     }
  798.     static intrinsic_charset & _get_not_digit_charset()
  799.     {
  800.         static intrinsic_charset s_not_digit_charset( true, _DIGIT, "" );
  801.         return s_not_digit_charset;
  802.     }
  803.     static intrinsic_charset & _get_not_space_charset()
  804.     {
  805.         static intrinsic_charset s_not_space_charset( true, _SPACE, "" );
  806.         return s_not_space_charset;
  807.     }
  808. public:
  809.     static charset const & get_word_charset()
  810.     {
  811.         return _get_word_charset();
  812.     }
  813.     static charset const & get_digit_charset()
  814.     {
  815.         return _get_digit_charset();
  816.     }
  817.     static charset const & get_space_charset()
  818.     {
  819.         return _get_space_charset();
  820.     }
  821.     static charset const & get_not_word_charset()
  822.     {
  823.         return _get_not_word_charset();
  824.     }
  825.     static charset const & get_not_digit_charset()
  826.     {
  827.         return _get_not_digit_charset();
  828.     }
  829.     static charset const & get_not_space_charset()
  830.     {
  831.         return _get_not_space_charset();
  832.     }
  833.     static void reset()
  834.     {
  835.         _get_word_charset().reset( false, _ALPHA|_DIGIT, "_" );
  836.         _get_digit_charset().reset( false, _DIGIT, "" );
  837.         _get_space_charset().reset( false, _SPACE, "" );
  838.         _get_not_word_charset().reset( true, _ALPHA|_DIGIT, "_" );
  839.         _get_not_digit_charset().reset( true, _DIGIT, "" );
  840.         _get_not_space_charset().reset( true, _SPACE, "" );
  841.     }
  842. };
  843. //
  844. // Operator implementations
  845. //
  846. // Evaluates the beginning-of-string condition
  847. template< typename CSTRINGS >
  848. struct bos_t
  849. {
  850.     template< typename CI >
  851.     static bool eval( match_param<CI> const & param, CI iter )
  852.     {
  853.         return param.ibegin == iter;
  854.     }
  855.     template< typename U > struct rebind { typedef bos_t<U> other; };
  856. };
  857. // Find the beginning of a line, either beginning of a string, or the character
  858. // immediately following a newline
  859. template< typename CSTRINGS >
  860. struct bol_t
  861. {
  862.     template< typename CI >
  863.     static bool eval( match_param<CI> const & param, CI iter )
  864.     {
  865.         typedef typename std::iterator_traits<CI>::value_type CH;
  866.         typedef std::char_traits<CH> traits_type;
  867.         return param.ibegin == iter || traits_type::eq( REGEX_CHAR(CH,'n'), *--iter );
  868.     }
  869.     template< typename U > struct rebind { typedef bol_t<U> other; };
  870. };
  871. // Evaluates end-of-string condition for string's
  872. template< typename CSTRINGS >
  873. struct eos_t
  874. {
  875.     template< typename CI >
  876.     static bool eval( match_param<CI> const & param, CI iter )
  877.     {
  878.         return param.istop == iter;
  879.     }
  880.     template< typename U > struct rebind { typedef eos_t<U> other; };
  881. };
  882. template<>
  883. struct eos_t<true_t>
  884. {
  885.     template< typename CI >
  886.     static bool eval( match_param<CI> const &, CI iter )
  887.     {
  888.         typedef typename std::iterator_traits<CI>::value_type CH;
  889.         typedef std::char_traits<CH> traits_type;
  890.         return traits_type::eq( REGEX_CHAR(CH,''), *iter );
  891.     }
  892.     template< typename U > struct rebind { typedef eos_t<U> other; };
  893. };
  894. // Evaluates end-of-line conditions, either the end of the string, or a
  895. // newline character.
  896. template< typename CSTRINGS >
  897. struct eol_t
  898. {
  899.     template< typename CI >
  900.     static bool eval( match_param<CI> const & param, CI iter )
  901.     {
  902.         typedef typename std::iterator_traits<CI>::value_type CH;
  903.         typedef std::char_traits<CH> traits_type;
  904.         return param.istop == iter
  905.             || traits_type::eq( REGEX_CHAR(CH,'n'), *iter );
  906.     }
  907.     template< typename U > struct rebind { typedef eol_t<U> other; };
  908. };
  909. template<>
  910. struct eol_t<true_t>
  911. {
  912.     template< typename CI >
  913.     static bool eval( match_param<CI> const &, CI iter )
  914.     {
  915.         typedef typename std::iterator_traits<CI>::value_type CH;
  916.         typedef std::char_traits<CH> traits_type;
  917.         return traits_type::eq( REGEX_CHAR(CH,''), *iter )
  918.             || traits_type::eq( REGEX_CHAR(CH,'n'), *iter );
  919.     }
  920.     template< typename U > struct rebind { typedef eol_t<U> other; };
  921. };
  922. // Evaluates perl's end-of-string conditions, either the end of the string, or a
  923. // newline character followed by end of string. ( Only used by $ and /Z assertions )
  924. template< typename CSTRINGS >
  925. struct peos_t
  926. {
  927.     template< typename CI >
  928.     static bool eval( match_param<CI> const & param, CI iter )
  929.     {
  930.         typedef typename std::iterator_traits<CI>::value_type CH;
  931.         typedef std::char_traits<CH> traits_type;
  932.         return param.istop == iter
  933.             || ( traits_type::eq( REGEX_CHAR(CH,'n'), *iter ) && param.istop == ++iter );
  934.     }
  935.     template< typename U > struct rebind { typedef peos_t<U> other; };
  936. };
  937. template<>
  938. struct peos_t<true_t>
  939. {
  940.     template< typename CI >
  941.     static bool eval( match_param<CI> const &, CI iter )
  942.     {
  943.         typedef typename std::iterator_traits<CI>::value_type CH;
  944.         typedef std::char_traits<CH> traits_type;
  945.         return traits_type::eq( REGEX_CHAR(CH,''), *iter )
  946.             || ( traits_type::eq( REGEX_CHAR(CH,'n'), *iter ) 
  947.                 && traits_type::eq( REGEX_CHAR(CH,''), *++iter ) );
  948.     }
  949.     template< typename U > struct rebind { typedef peos_t<U> other; };
  950. };
  951. // compare two characters, case-sensitive
  952. template< typename CH >
  953. struct ch_neq_t
  954. {
  955.     typedef CH char_type;
  956.     typedef std::char_traits<char_type> traits_type;
  957.     
  958.     static bool eval( register CH ch1, register CH ch2 )
  959.     {
  960.         return ! traits_type::eq( ch1, ch2 );
  961.     }
  962. };
  963. // Compare two characters, disregarding case
  964. template< typename CH >
  965. struct ch_neq_nocase_t
  966. {
  967.     typedef CH char_type;
  968.     typedef std::char_traits<char_type> traits_type;
  969.     
  970.     static bool eval( register CH ch1, register CH ch2 )
  971.     {
  972.         return ! traits_type::eq( regex_toupper( ch1 ), regex_toupper( ch2 ) );
  973.     }
  974. };
  975. //
  976. // helper functions for dealing with widths.
  977. //
  978. inline size_t width_add( size_t a, size_t b )
  979. {
  980.     return ( size_t( -1 ) == a || size_t( -1 ) == b ? size_t( -1 ) : a + b );
  981. }
  982. inline size_t width_mult( size_t a, size_t b )
  983. {
  984.     if( 0 == a || 0 == b )
  985.         return 0;
  986.     if( size_t( -1 ) == a || size_t( -1 ) == b )
  987.         return size_t( -1 );
  988.     return a * b;
  989. }
  990. inline bool operator==( width_type const & rhs, width_type const & lhs )
  991. {
  992.     return ( rhs.m_min == lhs.m_min && rhs.m_max == lhs.m_max );
  993. }
  994. inline bool operator!=( width_type const & rhs, width_type const & lhs )
  995. {
  996.     return ( rhs.m_min != lhs.m_min || rhs.m_max != lhs.m_max );
  997. }
  998. inline width_type operator+( width_type const & rhs, width_type const & lhs )
  999. {
  1000.     width_type width = { width_add( rhs.m_min, lhs.m_min ), width_add( rhs.m_max, lhs.m_max ) };
  1001.     return width;
  1002. }
  1003. inline width_type operator*( width_type const & rhs, width_type const & lhs )
  1004. {
  1005.     width_type width = { width_mult( rhs.m_min, lhs.m_min ), width_mult( rhs.m_max, lhs.m_max ) };
  1006.     return width;
  1007. }
  1008. inline width_type & operator+=( width_type & rhs, width_type const & lhs )
  1009. {
  1010.     rhs.m_min = width_add( rhs.m_min, lhs.m_min );
  1011.     rhs.m_max = width_add( rhs.m_max, lhs.m_max );
  1012.     return rhs;
  1013. }
  1014. inline width_type & operator*=( width_type & rhs, width_type const & lhs )
  1015. {
  1016.     rhs.m_min = width_mult( rhs.m_min, lhs.m_min );
  1017.     rhs.m_max = width_mult( rhs.m_max, lhs.m_max );
  1018.     return rhs;
  1019. }
  1020. width_type const zero_width = { 0, 0 };
  1021. width_type const worst_width = { 0, size_t( -1 ) };
  1022. template< typename CI >
  1023. struct width_param
  1024. {
  1025.     int cookie;
  1026.     width_type const total_width;
  1027.     std::vector<match_group_base<CI>*> & rggroups;
  1028.     std::list<size_t> const & invisible_groups;
  1029.     bool first_pass() const { return uninit_width() == total_width; }
  1030.     width_param(
  1031.         int cookie,
  1032.         width_type const & total_width,
  1033.         std::vector<match_group_base<CI>*> & rggroups,
  1034.         std::list<size_t> const & invisible_groups )
  1035.         : cookie( cookie ),
  1036.           total_width( total_width ),
  1037.           rggroups( rggroups ),
  1038.           invisible_groups( invisible_groups )
  1039.     {
  1040.     }
  1041. private:
  1042.     width_param & operator=( width_param const & );
  1043. };
  1044. // --------------------------------------------------------------------------
  1045. //
  1046. // Class:       sub_expr
  1047. //
  1048. // Description: patterns are "compiled" into a directed graph of sub_expr
  1049. //              structs.  Matching is accomplished by traversing this graph.
  1050. //
  1051. // Methods:     sub_expr             - construct a sub_expr
  1052. //              recursive_match_this_ - does this sub_expr match at the given location
  1053. //              width_this           - what is the width of this sub_expr
  1054. //              ~sub_expr            - recursively delete the sub_expr graph
  1055. //              next                 - pointer to the next node in the graph
  1056. //              next                 - pointer to the next node in the graph
  1057. //              recursive_match_next_ - match the rest of the graph
  1058. //              recursive_match_all_  - recursive_match_this_ and recursive_match_next_
  1059. //              is_assertion         - true if this sub_expr is a zero-width assertion
  1060. //              get_width            - find the width of the graph at this sub_expr
  1061. //
  1062. // Members:     m_pnext      - pointer to the next node in the graph
  1063. //
  1064. // History:     8/14/2000 - ericne - Created
  1065. //
  1066. // --------------------------------------------------------------------------
  1067. template< typename CI >
  1068. class sub_expr : public sub_expr_base<CI>
  1069. {
  1070.     sub_expr * m_pnext;
  1071. protected:
  1072.     // Only derived classes can instantiate sub_expr's
  1073.     sub_expr() 
  1074.         : m_pnext( NULL )
  1075.     {
  1076.     }
  1077. public:
  1078.     typedef CI const_iterator;
  1079.     typedef typename std::iterator_traits<CI>::value_type char_type;
  1080.     typedef std::char_traits<char_type> traits_type;
  1081.     virtual ~sub_expr()
  1082.     {
  1083.         delete m_pnext;
  1084.     }
  1085.     sub_expr ** pnext()
  1086.     {
  1087.         return & m_pnext;
  1088.     }
  1089.     sub_expr const * next() const
  1090.     {
  1091.         return m_pnext;
  1092.     }
  1093.     virtual sub_expr<CI> * quantify( size_t, size_t, bool, regex_arena & )
  1094.     {
  1095.         throw bad_regexpr( "sub-expression cannot be quantified" );
  1096.     }
  1097.     // Match this object and all subsequent objects
  1098.     // If recursive_match_all_ returns false, it must not change any of param's state
  1099.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  1100.     {
  1101.         return ( recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  1102.     }
  1103.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const // for C-style strings
  1104.     {
  1105.         return ( recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  1106.     }
  1107.     // match this object only
  1108.     virtual bool recursive_match_this_( match_param<CI> &, CI & ) const
  1109.     {
  1110.         return true;
  1111.     }
  1112.     virtual bool recursive_match_this_c( match_param<CI> &, CI & ) const // for C-style strings
  1113.     {
  1114.         return true;
  1115.     }
  1116.     // Match all subsequent objects
  1117.     template< typename CSTRINGS >
  1118.     bool recursive_match_next_( match_param<CI> & param, CI icur, CSTRINGS ) const
  1119.     {
  1120.         return ( m_pnext ) ? m_pnext->recursive_match_all_( param, icur, CSTRINGS() ) :
  1121.             ! ( param.no0len && param.istart == icur );
  1122.     }
  1123.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  1124.     {
  1125.         param.next = next();
  1126.         return true;
  1127.     }
  1128.     virtual bool iterative_match_this_c( match_param<CI> & param ) const // for C-style strings
  1129.     {
  1130.         param.next = next();
  1131.         return true;
  1132.     }
  1133.     virtual bool iterative_rematch_this_( match_param<CI> & ) const
  1134.     {
  1135.         return false;
  1136.     }
  1137.     virtual bool iterative_rematch_this_c( match_param<CI> & ) const // for C-style strings
  1138.     {
  1139.         return false;
  1140.     }
  1141.     virtual bool is_assertion() const
  1142.     {
  1143.         return false;
  1144.     }
  1145.     width_type get_width( width_param<CI> & param )
  1146.     {
  1147.         width_type temp_width = width_this( param );
  1148.         if( m_pnext )
  1149.             temp_width += m_pnext->get_width( param );
  1150.         return temp_width;
  1151.     }
  1152.     virtual width_type width_this( width_param<CI> & ) = 0;
  1153.     template< typename CSTRINGS >
  1154.     bool iterative_match_this_( match_param<CI> & param, CSTRINGS ) const
  1155.         { return sub_expr_base<CI>::iterative_match_this_( param, CSTRINGS() ); }
  1156.     template< typename CSTRINGS >
  1157.     bool iterative_rematch_this_( match_param<CI> & param, CSTRINGS ) const
  1158.         { return sub_expr_base<CI>::iterative_rematch_this_( param, CSTRINGS() ); }
  1159.     template< typename CSTRINGS >
  1160.     bool recursive_match_all_( match_param<CI> & param, CI icur, CSTRINGS ) const
  1161.         { return sub_expr_base<CI>::recursive_match_all_( param, icur, CSTRINGS() ); }
  1162. };
  1163. // Base class for sub-expressions which are zero-width
  1164. // ( i.e., assertions eat no characters during matching )
  1165. // Assertions cannot be quantified.
  1166. template< typename CI >
  1167. class assertion : public sub_expr<CI>
  1168. {
  1169. public:
  1170.     typedef typename sub_expr<CI>::const_iterator const_iterator;
  1171.     typedef typename sub_expr<CI>::char_type      char_type;
  1172.     virtual bool is_assertion() const
  1173.         { return true; }
  1174.     virtual width_type width_this( width_param<CI> & )
  1175.         { return zero_width; }
  1176. };
  1177. template< typename CI, typename OP >
  1178. class assert_op : public assertion<CI>
  1179. {
  1180. public:
  1181.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  1182.     {
  1183.         return ( assert_op::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  1184.     }
  1185.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  1186.     {
  1187.         return ( assert_op::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  1188.     }
  1189.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  1190.     {
  1191.         typedef typename OP::template rebind<false_t>::other op_t;
  1192.         return op_t::eval( param, icur );
  1193.     }
  1194.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  1195.     {
  1196.         typedef typename OP::template rebind<true_t>::other op_t;
  1197.         return op_t::eval( param, icur );
  1198.     }
  1199.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  1200.     {
  1201.         param.next = next();
  1202.         typedef typename OP::template rebind<false_t>::other op_t;
  1203.         return op_t::eval( param, param.icur );
  1204.     }
  1205.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  1206.     {
  1207.         param.next = next();
  1208.         typedef typename OP::template rebind<true_t>::other op_t;
  1209.         return op_t::eval( param, param.icur );
  1210.     }
  1211. };
  1212. template< typename CI >
  1213. inline assertion<CI> * create_bos( REGEX_FLAGS, regex_arena & arena )
  1214. {
  1215.     return new( arena ) assert_op<CI, bos_t<true_t> >();
  1216. }
  1217. template< typename CI >
  1218. inline assertion<CI> * create_eos( REGEX_FLAGS, regex_arena & arena )
  1219. {
  1220.     return new( arena ) assert_op<CI, peos_t<true_t> >();
  1221. }
  1222. template< typename CI >
  1223. inline assertion<CI> * create_eoz( REGEX_FLAGS, regex_arena & arena )
  1224. {
  1225.     return new( arena ) assert_op<CI, eos_t<true_t> >();
  1226. }
  1227. template< typename CI >
  1228. inline assertion<CI> * create_bol( REGEX_FLAGS flags, regex_arena & arena )
  1229. {
  1230.     switch( MULTILINE & flags )
  1231.     {
  1232.     case 0:
  1233.         return new( arena ) assert_op<CI, bos_t<true_t> >();
  1234.     case MULTILINE:
  1235.         return new( arena ) assert_op<CI, bol_t<true_t> >();
  1236.     default:
  1237.         __assume( 0 ); // tells the compiler that this is unreachable
  1238.     }
  1239. }
  1240. template< typename CI >
  1241. inline assertion<CI> * create_eol( REGEX_FLAGS flags, regex_arena & arena )
  1242. {
  1243.     switch( MULTILINE & flags )
  1244.     {
  1245.     case 0:
  1246.         return new( arena ) assert_op<CI, peos_t<true_t> >();
  1247.     case MULTILINE:
  1248.         return new( arena ) assert_op<CI, eol_t<true_t> >();
  1249.     default:
  1250.         __assume( 0 ); // tells the compiler that this is unreachable
  1251.     }
  1252. }
  1253. template< typename CI, typename SUB_EXPR = sub_expr<CI> >
  1254. class match_wrapper : public sub_expr<CI>
  1255. {
  1256.     match_wrapper & operator=( match_wrapper const & );
  1257. public:
  1258.     match_wrapper( SUB_EXPR * psub )
  1259.         : m_psub( psub )
  1260.     {
  1261.     }
  1262.     virtual ~match_wrapper()
  1263.     {
  1264.         _cleanup();
  1265.     }
  1266.     virtual width_type width_this( width_param<CI> & param )
  1267.     {
  1268.         return m_psub->width_this( param );
  1269.     }
  1270. protected:
  1271.     void _cleanup()
  1272.     {
  1273.         delete m_psub;
  1274.         m_psub = NULL;
  1275.     }
  1276.     SUB_EXPR * m_psub;
  1277. };
  1278. template< typename CI, typename SUB_EXPR = sub_expr<CI> >
  1279. class match_quantifier : public match_wrapper<CI, SUB_EXPR>
  1280. {
  1281.     match_quantifier & operator=( match_quantifier const & );
  1282. public:
  1283.     match_quantifier( SUB_EXPR * psub, size_t lbound, size_t ubound )
  1284.         : match_wrapper<CI, SUB_EXPR>( psub ), m_lbound( lbound ), m_ubound( ubound )
  1285.     {
  1286.     }
  1287.     virtual width_type width_this( width_param<CI> & param )
  1288.     {
  1289.         width_type this_width = match_wrapper<CI, SUB_EXPR>::width_this( param );
  1290.         width_type quant_width = { m_lbound, m_ubound };
  1291.         return this_width * quant_width;
  1292.     }
  1293. protected:
  1294.     size_t const m_lbound;
  1295.     size_t const m_ubound;
  1296. };
  1297. template< typename CI, typename SUB_EXPR >
  1298. class atom_quantifier : public match_quantifier<CI, SUB_EXPR>
  1299. {
  1300.     atom_quantifier & operator=( atom_quantifier const & );
  1301. public:
  1302.     atom_quantifier( SUB_EXPR * psub, size_t lbound, size_t ubound )
  1303.         : match_quantifier<CI, SUB_EXPR>( psub, lbound, ubound ) 
  1304.     {
  1305.     }
  1306. protected:
  1307.     void _push_frame( unsafe_stack * pstack, CI curr, size_t count ) const
  1308.     {
  1309.         std::pair<CI, size_t> p( curr, count );
  1310.         pstack->push( p );
  1311.     }
  1312.     void _pop_frame( match_param<CI> & param ) const
  1313.     {
  1314.         std::pair<CI, size_t> p;
  1315.         param.pstack->pop( p );
  1316.         param.icur = p.first;
  1317.     }
  1318. };
  1319. //template< typename CSTRINGS >
  1320. //struct inliner
  1321. //{
  1322. //    template< typename SUB_EXPR, typename CI >
  1323. //    __forceinline static bool iterative_match_this_( SUB_EXPR const * psub, match_param<CI> & param )
  1324. //    {
  1325. //        return psub->SUB_EXPR::iterative_match_this_( param );
  1326. //    }
  1327. //};
  1328. //template<>
  1329. //struct inliner<true_t>
  1330. //{
  1331. //    template< typename SUB_EXPR, typename CI >
  1332. //    __forceinline static bool iterative_match_this_( SUB_EXPR const * psub, match_param<CI> & param )
  1333. //    {
  1334. //        return psub->SUB_EXPR::iterative_match_this_c( param );
  1335. //    }
  1336. //};
  1337. template< typename CI, typename SUB_EXPR >
  1338. class max_atom_quantifier : public atom_quantifier<CI, SUB_EXPR>
  1339. {
  1340.     max_atom_quantifier & operator=( max_atom_quantifier const & );
  1341. public:
  1342.     max_atom_quantifier( SUB_EXPR * psub, size_t lbound, size_t ubound )
  1343.         : atom_quantifier<CI, SUB_EXPR>( psub, lbound, ubound )
  1344.     {
  1345.     }
  1346.     // Why a macro instead of a template, you ask?  Performance.  Due to a known
  1347.     // bug in the VC7 inline heuristic, I cannot get VC7 to inline the calls to 
  1348.     // m_psub methods unless I use these macros.  And the performance win is 
  1349.     // nothing to sneeze at. It's on the order of a 25% speed up to use a macro 
  1350.     // here instead of a template.
  1351. #define DECLARE_RECURSIVE_MATCH_ALL(cstrings,ext)                                                           
  1352.     virtual bool recursive_match_all ## ext( match_param<CI> & param, CI icur ) const                       
  1353.     {                                                                                                       
  1354.         /* In an ideal world, istart and cdiff would be members of a union */                               
  1355.         /* to conserve stack, but I don't know if CI is a POD type or not. */                               
  1356.         CI        istart   = icur;                                                                          
  1357.         ptrdiff_t cdiff    = 0; /* must be a signed integral type */                                        
  1358.         size_t    cmatches = 0;                                                                             
  1359.         /* greedily match as much as we can*/                                                               
  1360.         if( m_ubound && m_psub->SUB_EXPR::recursive_match_this ## ext( param, icur ) )                      
  1361.         {                                                                                                   
  1362.             if( 0 == ( cdiff = -std::distance( istart, icur ) ) )                                           
  1363.                 return recursive_match_next_( param, icur, cstrings() );                                    
  1364.             while( ++cmatches < m_ubound && m_psub->SUB_EXPR::recursive_match_this ## ext( param, icur ) ); 
  1365.         }                                                                                                   
  1366.         if( m_lbound > cmatches )                                                                           
  1367.             return false;                                                                                   
  1368.         /* try matching the rest of the pattern, and back off if necessary */                               
  1369.         for( ; ; --cmatches, std::advance( icur, ( int ) cdiff ) )                                          
  1370.         {                                                                                                   
  1371.             if( recursive_match_next_( param, icur, cstrings() ) )                                          
  1372.                 return true;                                                                                
  1373.             if( m_lbound == cmatches )                                                                      
  1374.                 return false;                                                                               
  1375.         }                                                                                                   
  1376.     }
  1377. #define DECLARE_ITERATIVE_MATCH_THIS(ext)                                                                   
  1378.     virtual bool iterative_match_this ## ext( match_param<CI> & param ) const                               
  1379.     {                                                                                                       
  1380.         CI istart = param.icur;                                                                             
  1381.         size_t cmatches = 0;                                                                                
  1382.         if( m_ubound && m_psub->SUB_EXPR::iterative_match_this ## ext( param ) )                            
  1383.         {                                                                                                   
  1384.             if( 0 == std::distance( istart, param.icur ) )                                                  
  1385.             {                                                                                               
  1386.                 cmatches = m_lbound;                                                                        
  1387.             }                                                                                               
  1388.             else                                                                                            
  1389.             {                                                                                               
  1390.                 while( ++cmatches < m_ubound && m_psub->SUB_EXPR::iterative_match_this ## ext( param ) );   
  1391.             }                                                                                               
  1392.         }                                                                                                   
  1393.         if( cmatches >= m_lbound )                                                                          
  1394.         {                                                                                                   
  1395.             _push_frame( param.pstack, istart, cmatches );                                                  
  1396.             param.next = next();                                                                            
  1397.             return true;                                                                                    
  1398.         }                                                                                                   
  1399.         param.icur = istart;                                                                                
  1400.         return false;                                                                                       
  1401.     }
  1402. #define DECLARE_ITERATIVE_REMATCH_THIS(ext)                                                                 
  1403.     virtual bool iterative_rematch_this ## ext( match_param<CI> & param ) const                             
  1404.     {                                                                                                       
  1405.         size_t & cmatches = param.pstack->top( static_init<std::pair<CI, size_t> >::value ).second;         
  1406.         if( m_lbound != cmatches )                                                                          
  1407.         {                                                                                                   
  1408.             --cmatches;                                                                                     
  1409.             m_psub->SUB_EXPR::iterative_rematch_this ## ext( param );                                       
  1410.             param.next = next();                                                                            
  1411.             return true;                                                                                    
  1412.         }                                                                                                   
  1413.         _pop_frame( param );                                                                                
  1414.         return false;                                                                                       
  1415.     }
  1416.     DECLARE_RECURSIVE_MATCH_ALL(false_t,_)
  1417.     DECLARE_RECURSIVE_MATCH_ALL(true_t,_c)
  1418.     DECLARE_ITERATIVE_MATCH_THIS(_)
  1419.     DECLARE_ITERATIVE_MATCH_THIS(_c)
  1420.     DECLARE_ITERATIVE_REMATCH_THIS(_)
  1421.     DECLARE_ITERATIVE_REMATCH_THIS(_c)
  1422.     //template< typename CSTRINGS >
  1423.     //__forceinline bool _iterative_match_this( match_param<CI> & param ) const
  1424.     //{
  1425.     //    CI istart = param.icur;
  1426.     //    size_t cmatches = 0;
  1427.     //    if( m_ubound && inliner<CSTRINGS>::iterative_match_this_( m_psub, param ) )
  1428.     //    {
  1429.     //        if( 0 == std::distance( istart, param.icur ) )
  1430.     //        {
  1431.     //            cmatches = m_lbound;
  1432.     //        }
  1433.     //        else
  1434.     //        {
  1435.     //            while( ++cmatches < m_ubound && inliner<CSTRINGS>::iterative_match_this_( m_psub, param ) );
  1436.     //        }
  1437.     //    }
  1438.     //    if( cmatches >= m_lbound )
  1439.     //    {
  1440.     //        _push_frame( param.pstack, istart, cmatches );
  1441.     //        param.next = next();
  1442.     //        return true;
  1443.     //    }
  1444.     //    param.icur = istart;
  1445.     //    return false;
  1446.     //}
  1447.     //virtual bool iterative_match_this_( match_param<CI> & param ) const
  1448.     //{
  1449.     //    return _iterative_match_this<false_t>( param );
  1450.     //}
  1451.     //virtual bool iterative_match_this_c( match_param<CI> & param ) const
  1452.     //{
  1453.     //    return _iterative_match_this<true_t>( param );
  1454.     //}
  1455. #undef DECLARE_RECURSIVE_MATCH_ALL
  1456. #undef DECLARE_ITERATIVE_MATCH_THIS
  1457. #undef DECLARE_ITERATIVE_REMATCH_THIS
  1458. };
  1459. template< typename CI, typename SUB_EXPR >
  1460. class min_atom_quantifier : public atom_quantifier<CI, SUB_EXPR>
  1461. {
  1462.     min_atom_quantifier & operator=( min_atom_quantifier const & );
  1463.     
  1464. public:
  1465.     min_atom_quantifier( SUB_EXPR * psub, size_t lbound, size_t ubound )
  1466.         : atom_quantifier<CI, SUB_EXPR>( psub, lbound, ubound )
  1467.     {
  1468.     }
  1469.     // Why a macro instead of a template, you ask?  Performance.  Due to a known
  1470.     // bug in the VC7 inline heuristic, I cannot get VC7 to inline the calls to 
  1471.     // m_psub methods unless I use these macros.  And the performance win is 
  1472.     // nothing to sneeze at. It's on the order of a 25% speed up to use a macro 
  1473.     // here instead of a template.
  1474. #define DECLARE_RECURSIVE_MATCH_ALL(cstrings,ext)                                                           
  1475.     virtual bool recursive_match_all ## ext( match_param<CI> & param, CI icur ) const                       
  1476.     {                                                                                                       
  1477.         CI     icur_tmp = icur;                                                                             
  1478.         size_t cmatches = 0;                                                                                
  1479.         if( m_psub->SUB_EXPR::recursive_match_this ## ext( param, icur_tmp ) )                              
  1480.         {                                                                                                   
  1481.             if( icur_tmp == icur )                                                                          
  1482.                 return recursive_match_next_( param, icur, cstrings() );                                    
  1483.             if( m_lbound )                                                                                  
  1484.             {                                                                                               
  1485.                 icur = icur_tmp;                                                                            
  1486.                 ++cmatches;                                                                                 
  1487.             }                                                                                               
  1488.             for( ; cmatches < m_lbound; ++cmatches )                                                        
  1489.             {                                                                                               
  1490.                 if( ! m_psub->SUB_EXPR::recursive_match_this ## ext( param, icur ) )                        
  1491.                     return false;                                                                           
  1492.             }                                                                                               
  1493.         }                                                                                                   
  1494.         else if( m_lbound )                                                                                 
  1495.         {                                                                                                   
  1496.             return false;                                                                                   
  1497.         }                                                                                                   
  1498.         do                                                                                                  
  1499.         {                                                                                                   
  1500.             if( recursive_match_next_( param, icur, cstrings() ) )                                          
  1501.                 return true;                                                                                
  1502.         }                                                                                                   
  1503.         while( cmatches < m_ubound &&                                                                       
  1504.              ( ++cmatches, m_psub->SUB_EXPR::recursive_match_this ## ext( param, icur ) ) );                
  1505.         return false;                                                                                       
  1506.     }
  1507. #define DECLARE_ITERATIVE_MATCH_THIS(ext)                                                                   
  1508.     virtual bool iterative_match_this ## ext( match_param<CI> & param ) const                               
  1509.     {                                                                                                       
  1510.         CI istart = param.icur;                                                                             
  1511.         size_t cmatches = 0;                                                                                
  1512.         if( m_psub->SUB_EXPR::iterative_match_this ## ext( param ) )                                        
  1513.         {                                                                                                   
  1514.             if( 0 == std::distance( istart, param.icur ) )                                                  
  1515.             {                                                                                               
  1516.                 cmatches = m_ubound;                                                                        
  1517.             }                                                                                               
  1518.             else if( m_lbound )                                                                             
  1519.             {                                                                                               
  1520.                 for( ++cmatches; cmatches < m_lbound; ++cmatches )                                          
  1521.                 {                                                                                           
  1522.                     if( ! m_psub->SUB_EXPR::iterative_match_this ## ext( param ) )                          
  1523.                     {                                                                                       
  1524.                         param.icur = istart;                                                                
  1525.                         return false;                                                                       
  1526.                     }                                                                                       
  1527.                 }                                                                                           
  1528.             }                                                                                               
  1529.             else                                                                                            
  1530.             {                                                                                               
  1531.                 param.icur = istart;                                                                        
  1532.             }                                                                                               
  1533.         }                                                                                                   
  1534.         else if( m_lbound )                                                                                 
  1535.         {                                                                                                   
  1536.             return false;                                                                                   
  1537.         }                                                                                                   
  1538.         _push_frame( param.pstack, istart, cmatches );                                                      
  1539.         param.next = next();                                                                                
  1540.         return true;                                                                                        
  1541.     }
  1542. #define DECLARE_ITERATIVE_REMATCH_THIS(ext)                                                                 
  1543.     virtual bool iterative_rematch_this ## ext( match_param<CI> & param ) const                             
  1544.     {                                                                                                       
  1545.         size_t & cmatches = param.pstack->top( static_init<std::pair<CI, size_t> >::value ).second;         
  1546.         if( cmatches == m_ubound || ! m_psub->SUB_EXPR::iterative_match_this ## ext( param ) )              
  1547.         {                                                                                                   
  1548.             _pop_frame( param );                                                                            
  1549.             return false;                                                                                   
  1550.         }                                                                                                   
  1551.         ++cmatches;                                                                                         
  1552.         param.next = next();                                                                                
  1553.         return true;                                                                                        
  1554.     }
  1555.     DECLARE_RECURSIVE_MATCH_ALL(false_t,_)
  1556.     DECLARE_RECURSIVE_MATCH_ALL(true_t,_c)
  1557.     DECLARE_ITERATIVE_MATCH_THIS(_)
  1558.     DECLARE_ITERATIVE_MATCH_THIS(_c)
  1559.     DECLARE_ITERATIVE_REMATCH_THIS(_)
  1560.     DECLARE_ITERATIVE_REMATCH_THIS(_c)
  1561. #undef DECLARE_RECURSIVE_MATCH_ALL
  1562. #undef DECLARE_ITERATIVE_MATCH_THIS
  1563. #undef DECLARE_ITERATIVE_REMATCH_THIS
  1564. };
  1565. template< typename CI >
  1566. class match_char : public sub_expr<CI>
  1567. {
  1568.     match_char & operator=( match_char const & );
  1569. public:
  1570.     typedef typename sub_expr<CI>::char_type char_type;
  1571.     match_char( char_type const & ch )
  1572.         : m_ch( ch ) 
  1573.     {
  1574.     }
  1575.     virtual width_type width_this( width_param<CI> & )
  1576.     {
  1577.         width_type width = { 1, 1 };
  1578.         return width;
  1579.     }
  1580.     virtual bool iterative_rematch_this_( match_param<CI> & param ) const
  1581.     {
  1582.         --param.icur;
  1583.         return false;
  1584.     }
  1585.     virtual bool iterative_rematch_this_c( match_param<CI> & param ) const
  1586.     {
  1587.         --param.icur;
  1588.         return false;
  1589.     }
  1590. protected:
  1591.     char_type const m_ch;
  1592. };
  1593. template< typename CI >
  1594. class match_char_t : public match_char<CI>
  1595. {
  1596.     match_char_t & operator=( match_char_t const & );
  1597. public:
  1598.     typedef typename match_char<CI>::char_type char_type;
  1599.     match_char_t( char_type ch )
  1600.         : match_char<CI>( ch ) 
  1601.     {
  1602.     }
  1603.     virtual sub_expr<CI> * quantify( size_t lbound, size_t ubound, bool greedy, regex_arena & arena )
  1604.     {
  1605.         if( greedy )
  1606.             return new( arena ) max_atom_quantifier<CI, match_char_t<CI> >( this, lbound, ubound );
  1607.         else
  1608.             return new( arena ) min_atom_quantifier<CI, match_char_t<CI> >( this, lbound, ubound );
  1609.     }
  1610.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  1611.     {
  1612.         return ( match_char_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  1613.     }
  1614.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  1615.     {
  1616.         return ( match_char_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  1617.     }
  1618.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  1619.     {
  1620.         return _do_match_this( param, icur, false_t() );
  1621.     }
  1622.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  1623.     {
  1624.         return _do_match_this( param, icur, true_t() );
  1625.     }
  1626.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  1627.     {
  1628.         param.next = next();
  1629.         return _do_match_this( param, param.icur, false_t() );
  1630.     }
  1631.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  1632.     {
  1633.         param.next = next();
  1634.         return _do_match_this( param, param.icur, true_t() );
  1635.     }
  1636. private:
  1637.     template< typename CSTRINGS >
  1638.     bool _do_match_this( match_param<CI> & param, CI & icur, CSTRINGS ) const
  1639.     {
  1640.         if( eos_t<CSTRINGS>::eval( param, icur ) || ! traits_type::eq( *icur, m_ch ) )
  1641.             return false;
  1642.         ++icur;
  1643.         return true;
  1644.     }
  1645. };
  1646. template< typename CI >
  1647. class match_char_nocase_t : public match_char<CI>
  1648. {
  1649.     match_char_nocase_t & operator=( match_char_nocase_t const & );
  1650. public:
  1651.     typedef typename match_char<CI>::char_type char_type;
  1652.     match_char_nocase_t( char_type lower, char_type upper )
  1653.         : match_char<CI>( upper ), m_ch_lower( lower ) 
  1654.     {
  1655.     }
  1656.     virtual sub_expr<CI> * quantify( size_t lbound, size_t ubound, bool greedy, regex_arena & arena )
  1657.     {
  1658.         if( greedy )
  1659.             return new( arena ) max_atom_quantifier<CI, match_char_nocase_t<CI> >( this, lbound, ubound );
  1660.         else
  1661.             return new( arena ) min_atom_quantifier<CI, match_char_nocase_t<CI> >( this, lbound, ubound );
  1662.     }
  1663.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  1664.     {
  1665.         return ( match_char_nocase_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  1666.     }
  1667.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  1668.     {
  1669.         return ( match_char_nocase_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  1670.     }
  1671.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  1672.     {
  1673.         return _do_match_this( param, icur, false_t() );
  1674.     }
  1675.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  1676.     {
  1677.         return _do_match_this( param, icur, true_t() );
  1678.     }
  1679.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  1680.     {
  1681.         param.next = next();
  1682.         return _do_match_this( param, param.icur, false_t() );
  1683.     }
  1684.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  1685.     {
  1686.         param.next = next();
  1687.         return _do_match_this( param, param.icur, true_t() );
  1688.     }
  1689. private:
  1690.     template< typename CSTRINGS >
  1691.     bool _do_match_this( match_param<CI> & param, CI & icur, CSTRINGS ) const
  1692.     {
  1693.         if( eos_t<CSTRINGS>::eval( param, icur ) ||
  1694.             ( ! traits_type::eq( *icur, m_ch ) &&
  1695.               ! traits_type::eq( *icur, m_ch_lower ) ) )
  1696.             return false;
  1697.         ++icur;
  1698.         return true;
  1699.     }
  1700.     char_type const  m_ch_lower;
  1701. };
  1702. template< typename CI >
  1703. inline match_char<CI> * create_char(
  1704.      typename std::iterator_traits<CI>::value_type ch,
  1705.      REGEX_FLAGS flags, regex_arena & arena )
  1706. {
  1707.     typedef typename std::iterator_traits<CI>::value_type CH;
  1708.     typedef std::char_traits<CH> traits_type;
  1709.     switch( NOCASE & flags )
  1710.     {
  1711.     case 0:
  1712.         return new( arena ) match_char_t<CI>( ch );
  1713.     case NOCASE:
  1714.         {
  1715.             CH lower = regex_tolower( ch );
  1716.             CH upper = regex_toupper( ch );
  1717.             if( traits_type::eq( lower, upper ) )
  1718.                 return new( arena ) match_char_t<CI>( ch );
  1719.             else
  1720.                 return new( arena ) match_char_nocase_t<CI>( lower, upper );
  1721.         }
  1722.     default:
  1723.         __assume( 0 ); // tells the compiler that this is unreachable
  1724.     }
  1725. }
  1726. template< typename CI >
  1727. class match_literal : public sub_expr<CI>
  1728. {
  1729.     match_literal & operator=( match_literal const & );
  1730. public:
  1731.     typedef typename sub_expr<CI>::char_type      char_type;
  1732.     typedef std::basic_string<char_type>          string_type;
  1733.     typedef typename string_type::iterator        iterator;
  1734.     typedef typename string_type::const_iterator  const_iterator;
  1735.     match_literal( const_iterator istart, const_iterator istop )
  1736.         : m_istart( istart ), m_istop( istop ), m_dist( std::distance( m_istart, m_istop ) )
  1737.     {
  1738.     }
  1739.     const_iterator const m_istart;
  1740.     const_iterator const m_istop;
  1741.     ptrdiff_t const m_dist; // must be signed integral type
  1742.     virtual width_type width_this( width_param<CI> & )
  1743.     {
  1744.         width_type width = { ( size_t ) m_dist, ( size_t ) m_dist };
  1745.         return width;
  1746.     }
  1747.     virtual bool iterative_rematch_this_( match_param<CI> & param ) const
  1748.     {
  1749.         std::advance( param.icur, ( int ) - m_dist );
  1750.         return false;
  1751.     }
  1752.     virtual bool iterative_rematch_this_c( match_param<CI> & param ) const
  1753.     {
  1754.         std::advance( param.icur, ( int ) - m_dist );
  1755.         return false;
  1756.     }
  1757. };
  1758. template< typename CI >
  1759. class match_literal_t : public match_literal<CI>
  1760. {
  1761.     match_literal_t & operator=( match_literal_t const & );
  1762. public:
  1763.     typedef typename match_literal<CI>::char_type       char_type;
  1764.     typedef typename match_literal<CI>::string_type     string_type;
  1765.     typedef typename match_literal<CI>::iterator        iterator;
  1766.     typedef typename match_literal<CI>::const_iterator  const_iterator;
  1767.     match_literal_t( const_iterator istart, const_iterator istop )
  1768.         : match_literal<CI>( istart, istop )
  1769.     {
  1770.     }
  1771.     virtual sub_expr<CI> * quantify( size_t lbound, size_t ubound, bool greedy, regex_arena & arena )
  1772.     {
  1773.         if( greedy )
  1774.             return new( arena ) max_atom_quantifier<CI, match_literal_t<CI> >( this, lbound, ubound );
  1775.         else
  1776.             return new( arena ) min_atom_quantifier<CI, match_literal_t<CI> >( this, lbound, ubound );
  1777.     }
  1778.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  1779.     {
  1780.         return ( match_literal_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  1781.     }
  1782.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  1783.     {
  1784.         return ( match_literal_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  1785.     }
  1786.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  1787.     {
  1788.         return _do_match_this( param, icur, false_t() );
  1789.     }
  1790.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  1791.     {
  1792.         return _do_match_this( param, icur, true_t() );
  1793.     }
  1794.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  1795.     {
  1796.         param.next = next();
  1797.         return _do_match_this( param, param.icur, false_t() );
  1798.     }
  1799.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  1800.     {
  1801.         param.next = next();
  1802.         return _do_match_this( param, param.icur, true_t() );
  1803.     }
  1804. private:
  1805.     template< typename CSTRINGS >
  1806.     bool _do_match_this( match_param<CI> & param, CI & icur, CSTRINGS ) const
  1807.     {
  1808.         CI icur_tmp = icur;
  1809.         const_iterator ithis = m_istart;
  1810.         for( ; m_istop != ithis; ++icur_tmp, ++ithis )
  1811.         {
  1812.             if( eos_t<CSTRINGS>::eval( param, icur_tmp ) || ! traits_type::eq( *ithis, *icur_tmp ) )
  1813.                 return false;
  1814.         }
  1815.         icur = icur_tmp;
  1816.         return true;
  1817.     }
  1818. };
  1819. template< typename CI >
  1820. class match_literal_nocase_t : public match_literal<CI>
  1821. {
  1822.     match_literal_nocase_t & operator=( match_literal_nocase_t const & );
  1823. public:
  1824.     typedef typename match_literal<CI>::char_type       char_type;
  1825.     typedef typename match_literal<CI>::string_type     string_type;
  1826.     typedef typename match_literal<CI>::iterator        iterator;
  1827.     typedef typename match_literal<CI>::const_iterator  const_iterator;
  1828.     match_literal_nocase_t( iterator istart, const_iterator istop, regex_arena & arena )
  1829.         : match_literal<CI>( istart, istop ),
  1830.           m_szlower( regex_allocator<char_type>( arena ).allocate( ( size_t ) m_dist ) )
  1831.     {
  1832.         // Copy from istart to m_szlower
  1833.         std::copy( m_istart, m_istop, m_szlower );
  1834.         // Store the uppercase version of the literal in [ m_istart, m_istop ).
  1835.         regex_toupper( istart, istop );
  1836.         // Store the lowercase version of the literal in m_strlower.
  1837.         regex_tolower( m_szlower, static_cast<char_type const *>( m_szlower + m_dist ) );
  1838.     }
  1839.     virtual sub_expr<CI> * quantify( size_t lbound, size_t ubound, bool greedy, regex_arena & arena )
  1840.     {
  1841.         if( greedy )
  1842.             return new( arena ) max_atom_quantifier<CI, match_literal_nocase_t<CI> >( this, lbound, ubound );
  1843.         else
  1844.             return new( arena ) min_atom_quantifier<CI, match_literal_nocase_t<CI> >( this, lbound, ubound );
  1845.     }
  1846.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  1847.     {
  1848.         return ( match_literal_nocase_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  1849.     }
  1850.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  1851.     {
  1852.         return ( match_literal_nocase_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  1853.     }
  1854.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  1855.     {
  1856.         return _do_match_this( param, icur, false_t() );
  1857.     }
  1858.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  1859.     {
  1860.         return _do_match_this( param, icur, true_t() );
  1861.     }
  1862.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  1863.     {
  1864.         param.next = next();
  1865.         return _do_match_this( param, param.icur, false_t() );
  1866.     }
  1867.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  1868.     {
  1869.         param.next = next();
  1870.         return _do_match_this( param, param.icur, true_t() );
  1871.     }
  1872. private:
  1873.     // Allocated from a regex arena. The memory will be cleaned up
  1874.     // when the arena is deallocated.
  1875.     char_type *const m_szlower;
  1876.     template< typename CSTRINGS >
  1877.     bool _do_match_this( match_param<CI> & param, CI & icur, CSTRINGS ) const
  1878.     {
  1879.         CI icur_tmp = icur;
  1880.         const_iterator ithisu    = m_istart;  // uppercase
  1881.         char_type const * ithisl = m_szlower; // lowercase
  1882.         for( ; m_istop != ithisu; ++icur_tmp, ++ithisu, ++ithisl )
  1883.         {
  1884.             if( eos_t<CSTRINGS>::eval( param, icur_tmp ) ||
  1885.                 ( ! traits_type::eq( *ithisu, *icur_tmp ) &&
  1886.                   ! traits_type::eq( *ithisl, *icur_tmp ) ) )
  1887.                 return false;
  1888.         }
  1889.         icur = icur_tmp;
  1890.         return true;
  1891.     }
  1892. };
  1893. template< typename CI, typename II1, typename II2 >
  1894. inline sub_expr<CI> * create_literal(
  1895.      II1 istart, II2 istop, REGEX_FLAGS flags, regex_arena & arena )
  1896. {
  1897.     // a match_char is faster than a match_literal, so prefer it when
  1898.     // the literal is only 1 char wide
  1899.     if( 1 == std::distance<II2>( istart, istop ) )
  1900.     {
  1901.         return create_char<CI>( *istart, flags, arena );
  1902.     }
  1903.     switch( NOCASE & flags )
  1904.     {
  1905.     case 0:
  1906.         return new( arena ) match_literal_t<CI>( istart, istop );
  1907.     case NOCASE:
  1908.         return new( arena ) match_literal_nocase_t<CI>( istart, istop, arena );
  1909.     default:
  1910.         __assume( 0 ); // tells the compiler that this is unreachable
  1911.     }
  1912. }
  1913. template< typename CI >
  1914. class match_any : public sub_expr<CI>
  1915. {
  1916. public:
  1917.     virtual width_type width_this( width_param<CI> & )
  1918.     {
  1919.         width_type width = { 1, 1 };
  1920.         return width;
  1921.     }
  1922.     virtual bool iterative_rematch_this_( match_param<CI> & param ) const
  1923.     {
  1924.         --param.icur;
  1925.         return false;
  1926.     }
  1927.     virtual bool iterative_rematch_this_c( match_param<CI> & param ) const
  1928.     {
  1929.         --param.icur;
  1930.         return false;
  1931.     }
  1932. };
  1933. template< typename CI, typename EOS >
  1934. class match_any_t : public match_any<CI>
  1935. {
  1936.     template< typename CSTRINGS >
  1937.     static bool _do_match_this( match_param<CI> & param, CI & icur, CSTRINGS )
  1938.     {
  1939.         typedef typename EOS::template rebind<CSTRINGS>::other op_t;
  1940.         if( op_t::eval( param, icur ) )
  1941.             return false;
  1942.         ++icur;
  1943.         return true;
  1944.     }
  1945. public:
  1946.     virtual sub_expr<CI> * quantify( size_t lbound, size_t ubound, bool greedy, regex_arena & arena )
  1947.     {
  1948.         if( greedy )
  1949.             return new( arena ) max_atom_quantifier<CI, match_any_t<CI, EOS> >( this, lbound, ubound );
  1950.         else
  1951.             return new( arena ) min_atom_quantifier<CI, match_any_t<CI, EOS> >( this, lbound, ubound );
  1952.     }
  1953.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  1954.     {
  1955.         return ( match_any_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  1956.     }
  1957.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  1958.     {
  1959.         return ( match_any_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  1960.     }
  1961.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  1962.     {
  1963.         return _do_match_this( param, icur, false_t() );
  1964.     }
  1965.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  1966.     {
  1967.         return _do_match_this( param, icur, true_t() );
  1968.     }
  1969.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  1970.     {
  1971.         param.next = next();
  1972.         return _do_match_this( param, param.icur, false_t() );
  1973.     }
  1974.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  1975.     {
  1976.         param.next = next();
  1977.         return _do_match_this( param, param.icur, true_t() );
  1978.     }
  1979. };
  1980. template< typename CI >
  1981. inline match_any<CI> * create_any( REGEX_FLAGS flags, regex_arena & arena )
  1982. {
  1983.     switch( SINGLELINE & flags )
  1984.     {
  1985.     case 0:
  1986.         return new( arena ) match_any_t<CI, eol_t<true_t> >();
  1987.     case SINGLELINE:
  1988.         return new( arena ) match_any_t<CI, eos_t<true_t> >();
  1989.     default:
  1990.         __assume( 0 ); // tells the compiler that this is unreachable
  1991.     }
  1992. }
  1993. template< typename CI >
  1994. class match_charset : public sub_expr<CI>
  1995. {
  1996. public:
  1997.     virtual width_type width_this( width_param<CI> & )
  1998.     {
  1999.         width_type width = { 1, 1 };
  2000.         return width;
  2001.     }
  2002.     virtual bool iterative_rematch_this_( match_param<CI> & param ) const
  2003.     {
  2004.         --param.icur;
  2005.         return false;
  2006.     }
  2007.     virtual bool iterative_rematch_this_c( match_param<CI> & param ) const
  2008.     {
  2009.         --param.icur;
  2010.         return false;
  2011.     }
  2012. };
  2013. template< typename CI, bool CASE >
  2014. class match_charset_t : public match_charset<CI>
  2015. {
  2016.     charset const & m_cs; // ref to an intrinsic charset ( possibly user-defined )
  2017.     match_charset_t & operator=( match_charset_t const & );
  2018.     template< typename CSTRINGS >
  2019.     bool _do_match_this( match_param<CI> & param, CI & icur, CSTRINGS ) const
  2020.     {
  2021.         if( eos_t<CSTRINGS>::eval( param, icur ) || ! m_cs.in( *icur, bool2type<CASE>() ) )
  2022.             return false;
  2023.         ++icur;
  2024.         return true;
  2025.     }
  2026. public:
  2027.     match_charset_t( charset const & cs )
  2028.          : m_cs( cs ) 
  2029.     {
  2030.     }
  2031.     virtual sub_expr<CI> * quantify( size_t lbound, size_t ubound, bool greedy, regex_arena & arena )
  2032.     {
  2033.         if( greedy )
  2034.             return new( arena ) max_atom_quantifier<CI, match_charset_t<CI, CASE> >( this, lbound, ubound );
  2035.         else
  2036.             return new( arena ) min_atom_quantifier<CI, match_charset_t<CI, CASE> >( this, lbound, ubound );
  2037.     }
  2038.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  2039.     {
  2040.         return ( match_charset_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  2041.     }
  2042.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  2043.     {
  2044.         return ( match_charset_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  2045.     }
  2046.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  2047.     {
  2048.         return _do_match_this( param, icur, false_t() );
  2049.     }
  2050.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  2051.     {
  2052.         return _do_match_this( param, icur, true_t() );
  2053.     }
  2054.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  2055.     {
  2056.         param.next = next();
  2057.         return _do_match_this( param, param.icur, false_t() );
  2058.     }
  2059.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  2060.     {
  2061.         param.next = next();
  2062.         return _do_match_this( param, param.icur, true_t() );
  2063.     }
  2064. };
  2065. template< typename CI, bool CASE >
  2066. class match_custom_charset_t : public match_charset<CI>
  2067. {
  2068.     std::auto_ptr<custom_charset const> m_pcs; // ptr to a custom charset alloc'ed in regex arena
  2069.     template< typename CSTRINGS >
  2070.     bool _do_match_this( match_param<CI> & param, CI & icur, CSTRINGS ) const
  2071.     {
  2072.         if( eos_t<CSTRINGS>::eval( param, icur ) || ! m_pcs->in( *icur, bool2type<CASE>() ) )
  2073.             return false;
  2074.         ++icur;
  2075.         return true;
  2076.     }
  2077. public:
  2078.     match_custom_charset_t( custom_charset const * pcs )
  2079.          : m_pcs( pcs ) 
  2080.     {
  2081.     }
  2082.     virtual sub_expr<CI> * quantify( size_t lbound, size_t ubound, bool greedy, regex_arena & arena )
  2083.     {
  2084.         if( greedy )
  2085.             return new( arena ) max_atom_quantifier<CI, match_custom_charset_t<CI, CASE> >( this, lbound, ubound );
  2086.         else
  2087.             return new( arena ) min_atom_quantifier<CI, match_custom_charset_t<CI, CASE> >( this, lbound, ubound );
  2088.     }
  2089.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  2090.     {
  2091.         return ( match_custom_charset_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  2092.     }
  2093.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  2094.     {
  2095.         return ( match_custom_charset_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  2096.     }
  2097.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  2098.     {
  2099.         return _do_match_this( param, icur, false_t() );
  2100.     }
  2101.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  2102.     {
  2103.         return _do_match_this( param, icur, true_t() );
  2104.     }
  2105.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  2106.     {
  2107.         param.next = next();
  2108.         return _do_match_this( param, param.icur, false_t() );
  2109.     }
  2110.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  2111.     {
  2112.         param.next = next();
  2113.         return _do_match_this( param, param.icur, true_t() );
  2114.     }
  2115. };
  2116. template< typename CI >
  2117. inline match_charset<CI> * create_charset(
  2118.      charset const & charset,
  2119.      REGEX_FLAGS flags, regex_arena & arena )
  2120. {
  2121.     switch( NOCASE & flags )
  2122.     {
  2123.     case 0:
  2124.         return new( arena ) match_charset_t<CI, true>( charset );
  2125.     case NOCASE:
  2126.         return new( arena ) match_charset_t<CI, false>( charset );
  2127.     default:
  2128.         __assume( 0 ); // tells the compiler that this is unreachable
  2129.     }
  2130. }
  2131. template< typename CI >
  2132. inline match_charset<CI> * create_custom_charset(
  2133.      custom_charset const * pcharset,
  2134.      REGEX_FLAGS flags, regex_arena & arena )
  2135. {
  2136.     switch( NOCASE & flags )
  2137.     {
  2138.     case 0:
  2139.         return new( arena ) match_custom_charset_t<CI, true>( pcharset );
  2140.     case NOCASE:
  2141.         return new( arena ) match_custom_charset_t<CI, false>( pcharset );
  2142.     default:
  2143.         __assume( 0 ); // tells the compiler that this is unreachable
  2144.     }
  2145. }
  2146. template< typename CI >
  2147. class word_assertion_t : public assertion<CI>
  2148. {
  2149.     word_assertion_t & operator=( word_assertion_t const & );
  2150. public:
  2151.     typedef typename assertion<CI>::char_type char_type;
  2152.     word_assertion_t()
  2153.         : m_isword( intrinsic_charsets<char_type>::get_word_charset() ) 
  2154.     {
  2155.     }
  2156. protected:
  2157.     charset const & m_isword;
  2158. };
  2159. template< typename CI >
  2160. class word_boundary_t : public word_assertion_t<CI>
  2161. {
  2162.     word_boundary_t & operator=( word_boundary_t const & );
  2163.     template< typename CSTRINGS >
  2164.     bool _do_match_this( match_param<CI> & param, CI icur, CSTRINGS ) const
  2165.     {
  2166.         bool const fthisword = ! eos_t<CSTRINGS>::eval( param, icur ) && m_isword.in( *icur, true_t()  );
  2167.         bool const fprevword = ! bos_t<CSTRINGS>::eval( param, icur ) && m_isword.in( *--icur, true_t() );
  2168.         return ( m_fisboundary == ( fprevword != fthisword ) );
  2169.     }
  2170. public:
  2171.     word_boundary_t( bool const fisboundary )
  2172.         : m_fisboundary( fisboundary ) 
  2173.     {
  2174.     }
  2175.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  2176.     {
  2177.         return ( word_boundary_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  2178.     }
  2179.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  2180.     {
  2181.         return ( word_boundary_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  2182.     }
  2183.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  2184.     {
  2185.         return _do_match_this( param, icur, false_t() );
  2186.     }
  2187.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  2188.     {
  2189.         return _do_match_this( param, icur, true_t() );
  2190.     }
  2191.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  2192.     {
  2193.         param.next = next();
  2194.         return _do_match_this( param, param.icur, false_t() );
  2195.     }
  2196.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  2197.     {
  2198.         param.next = next();
  2199.         return _do_match_this( param, param.icur, true_t() );
  2200.     }
  2201. protected:
  2202.     bool const m_fisboundary;
  2203. };
  2204. template< typename CI >
  2205. class word_start_t : public word_assertion_t<CI>
  2206. {
  2207.     word_start_t & operator=( word_start_t const & );
  2208.     template< typename CSTRINGS >
  2209.     bool _do_match_this( match_param<CI> & param, CI icur, CSTRINGS ) const
  2210.     {
  2211.         bool const fthisword = ! eos_t<CSTRINGS>::eval( param, icur ) && m_isword.in( *icur, true_t()  );
  2212.         bool const fprevword = ! bos_t<CSTRINGS>::eval( param, icur ) && m_isword.in( *--icur, true_t() );
  2213.         return ! fprevword && fthisword;
  2214.     }
  2215. public:
  2216.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  2217.     {
  2218.         return ( word_start_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  2219.     }
  2220.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  2221.     {
  2222.         return ( word_start_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  2223.     }
  2224.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  2225.     {
  2226.         return _do_match_this( param, icur, false_t() );
  2227.     }
  2228.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  2229.     {
  2230.         return _do_match_this( param, icur, true_t() );
  2231.     }
  2232.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  2233.     {
  2234.         param.next = next();
  2235.         return _do_match_this( param, param.icur, false_t() );
  2236.     }
  2237.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  2238.     {
  2239.         param.next = next();
  2240.         return _do_match_this( param, param.icur, true_t() );
  2241.     }
  2242. };
  2243. template< typename CI >
  2244. class word_stop_t : public word_assertion_t<CI>
  2245. {
  2246.     word_stop_t & operator=( word_stop_t const & );
  2247.     template< typename CSTRINGS >
  2248.     bool _do_match_this( match_param<CI> & param, CI icur, CSTRINGS ) const
  2249.     {
  2250.         bool const fthisword = ! eos_t<CSTRINGS>::eval( param, icur ) && m_isword.in( *icur, true_t()  );
  2251.         bool const fprevword = ! bos_t<CSTRINGS>::eval( param, icur ) && m_isword.in( *--icur, true_t() );
  2252.         return fprevword && ! fthisword;
  2253.     }
  2254. public:
  2255.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  2256.     {
  2257.         return ( word_stop_t::recursive_match_this_( param, icur ) && recursive_match_next_( param, icur, false_t() ) );
  2258.     }
  2259.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  2260.     {
  2261.         return ( word_stop_t::recursive_match_this_c( param, icur ) && recursive_match_next_( param, icur, true_t() ) );
  2262.     }
  2263.     virtual bool recursive_match_this_( match_param<CI> & param, CI & icur ) const
  2264.     {
  2265.         return _do_match_this( param, icur, false_t() );
  2266.     }
  2267.     virtual bool recursive_match_this_c( match_param<CI> & param, CI & icur ) const
  2268.     {
  2269.         return _do_match_this( param, icur, true_t() );
  2270.     }
  2271.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  2272.     {
  2273.         param.next = next();
  2274.         return _do_match_this( param, param.icur, false_t() );
  2275.     }
  2276.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  2277.     {
  2278.         param.next = next();
  2279.         return _do_match_this( param, param.icur, true_t() );
  2280.     }
  2281. };
  2282. template< typename CI >
  2283. inline assertion<CI> * create_word_boundary(
  2284.     bool const fisboundary,
  2285.     REGEX_FLAGS, regex_arena & arena )
  2286. {
  2287.     return new( arena ) word_boundary_t<CI>( fisboundary );
  2288. }
  2289. template< typename CI >
  2290. inline assertion<CI> * create_word_start( REGEX_FLAGS, regex_arena & arena )
  2291. {
  2292.     return new( arena ) word_start_t<CI>();
  2293. }
  2294. template< typename CI >
  2295. inline assertion<CI> * create_word_stop( REGEX_FLAGS, regex_arena & arena )
  2296. {
  2297.     return new( arena ) word_stop_t<CI>();
  2298. }
  2299. typedef std::pair<size_t, size_t> extent;
  2300. template< typename CI > class max_group_quantifier;
  2301. template< typename CI > class min_group_quantifier;
  2302. template< typename CI >
  2303. class match_group_base : public sub_expr<CI>
  2304. {
  2305. protected:
  2306.     typedef std::list<sub_expr<CI>*, REGEX_ALLOCATOR<sub_expr<CI>*> > alt_list_type;
  2307. private:
  2308.     match_group_base & operator=( match_group_base const & );
  2309.     void _push_frame( match_param<CI> & param ) const
  2310.     {
  2311.         unsafe_stack * ps = param.pstack;
  2312.         if( size_t( -1 ) != m_cgroup )
  2313.         {
  2314.             CI & reserved1 = ( *param.prgbackrefs )[ m_cgroup ].reserved1;
  2315.             ps->push( reserved1 );
  2316.             reserved1 = param.icur;
  2317.         }
  2318.         ps->push( m_rgalternates.begin() );
  2319.     }
  2320.     void _pop_frame( match_param<CI> & param ) const
  2321.     {
  2322.         typedef typename alt_list_type::const_iterator iter_type;
  2323.         unsafe_stack * ps = param.pstack;
  2324.         iter_type it;
  2325.         ps->pop( it );
  2326.         if( size_t( -1 ) != m_cgroup )
  2327.             ps->pop( ( *param.prgbackrefs )[ m_cgroup ].reserved1 );
  2328.     }
  2329.     template< typename CSTRINGS >
  2330.     bool _recursive_match_all( match_param<CI> & param, CI icur, CSTRINGS ) const
  2331.     {
  2332.         typedef typename alt_list_type::const_iterator LCI;
  2333.         if( size_t( -1 ) != m_cgroup ) // could be -1 if this is a lookahead_assertion
  2334.         {
  2335.             CI old_istart = ( *param.prgbackrefs )[ m_cgroup ].reserved1;
  2336.             ( *param.prgbackrefs )[ m_cgroup ].reserved1 = icur;
  2337.             for( LCI ialt = m_rgalternates.begin(); ialt != m_rgalternates.end(); ++ialt )
  2338.             {
  2339.                 if( (*ialt)->recursive_match_all_( param, icur, CSTRINGS() ) )
  2340.                     return true;
  2341.             }
  2342.             ( *param.prgbackrefs )[ m_cgroup ].reserved1 = old_istart;
  2343.         }
  2344.         else
  2345.         {
  2346.             for( LCI ialt = m_rgalternates.begin(); ialt != m_rgalternates.end(); ++ialt )
  2347.             {
  2348.                 if( (*ialt)->recursive_match_all_( param, icur, CSTRINGS() ) )
  2349.                     return true;
  2350.             }
  2351.         }
  2352.         return false;
  2353.     }
  2354.     bool _iterative_match_this( match_param<CI> & param ) const
  2355.     {
  2356.         _push_frame( param );
  2357.         param.next = m_rgalternates.front();
  2358.         return true;
  2359.     }
  2360.     bool _iterative_rematch_this( match_param<CI> & param ) const
  2361.     {
  2362.         typedef typename alt_list_type::const_iterator LCI;
  2363.         LCI next_iter = ++param.pstack->top( LCI() );
  2364.         if( next_iter != m_rgalternates.end() )
  2365.         {
  2366.             param.next = *next_iter;
  2367.             return true;
  2368.         }
  2369.         _pop_frame( param );
  2370.         return false;
  2371.     }
  2372. public:
  2373.     match_group_base( size_t cgroup, regex_arena & arena )
  2374.         : m_rgalternates( MAKE_ALLOCATOR(sub_expr<CI>const*,arena) ),
  2375.           m_pptail( NULL ), m_cgroup( cgroup ), m_nwidth( uninit_width() )
  2376.     {
  2377.     }
  2378.     // Derived classes that own the end_group object must have a
  2379.     // destructor, and that destructor must call _cleanup().
  2380.     virtual ~match_group_base() = 0;
  2381.     virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  2382.     {
  2383.         return _recursive_match_all( param, icur, false_t() );
  2384.     }
  2385.     virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  2386.     {
  2387.         return _recursive_match_all( param, icur, true_t() );
  2388.     }
  2389.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  2390.     {
  2391.         return _iterative_match_this( param );
  2392.     }
  2393.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  2394.     {
  2395.         return _iterative_match_this( param );
  2396.     }
  2397.     virtual bool iterative_rematch_this_( match_param<CI> & param ) const
  2398.     {
  2399.         return _iterative_rematch_this( param );
  2400.     }
  2401.     virtual bool iterative_rematch_this_c( match_param<CI> & param ) const
  2402.     {
  2403.         return _iterative_rematch_this( param );
  2404.     }
  2405.     size_t group_number() const
  2406.     {
  2407.         return m_cgroup;
  2408.     }
  2409.     void add_item( sub_expr<CI> * pitem )
  2410.     {
  2411.         *m_pptail = pitem;
  2412.         m_pptail = pitem->pnext();
  2413.     }
  2414.     void add_alternate()
  2415.     {
  2416.         m_rgalternates.push_back( NULL );
  2417.         m_pptail = & m_rgalternates.back();
  2418.     }
  2419.     void end_alternate()
  2420.     {
  2421.         *m_pptail = _get_end_group();
  2422.     }
  2423.     size_t calternates() const
  2424.     {
  2425.         return m_rgalternates.size();
  2426.     }
  2427.     virtual void set_extent( extent const & )
  2428.     {
  2429.     }
  2430.     width_type group_width( std::vector<match_group_base<CI>*> & rggroups,
  2431.                             std::list<size_t> const & invisible_groups )
  2432.     {
  2433.         assert( 0 == m_cgroup );
  2434.         // This should only be called on the top node
  2435.         if( uninit_width() == m_nwidth )
  2436.         {
  2437.             width_param<CI> param1( 0, uninit_width(), rggroups, invisible_groups );
  2438.             match_group_base<CI>::width_this( param1 );
  2439.             // If someone incremented the cookie, then we need a second pass
  2440.             if( 0 != param1.cookie && worst_width != m_nwidth )
  2441.             {
  2442.                 width_param<CI> param2( 0, m_nwidth, rggroups, invisible_groups );
  2443.                 match_group_base<CI>::width_this( param2 );
  2444.                 assert( 0 == param2.cookie );
  2445.             }
  2446.         }
  2447.         return m_nwidth;
  2448.     }
  2449.     virtual width_type width_this( width_param<CI> & param )
  2450.     {
  2451.         width_type width = { size_t( -1 ), 0 };
  2452.         typedef typename alt_list_type::iterator LCI;
  2453.         for( LCI ialt = m_rgalternates.begin(); worst_width != width && ialt != m_rgalternates.end(); ++ialt )
  2454.         {
  2455.             // prevent possible infinite recursion
  2456.             if( m_cgroup < param.rggroups.size() )
  2457.                 param.rggroups[ m_cgroup ] = NULL;
  2458.             width_type temp_width = ( *ialt )->get_width( param );
  2459.             if( m_cgroup < param.rggroups.size() )
  2460.                 param.rggroups[ m_cgroup ] = this;
  2461.             width.m_min = (std::min)( width.m_min, temp_width.m_min );
  2462.             width.m_max = (std::max)( width.m_max, temp_width.m_max );
  2463.         }
  2464.         return m_nwidth = width;
  2465.     }
  2466. protected:
  2467.     void _cleanup()
  2468.     {
  2469.         typedef typename alt_list_type::const_iterator LCI;
  2470.         for( LCI ialt = m_rgalternates.begin(); ialt != m_rgalternates.end(); ++ialt )
  2471.             delete *ialt;
  2472.         m_rgalternates.clear();
  2473.     }
  2474.     virtual sub_expr<CI> * _get_end_group() = 0;
  2475.     alt_list_type    m_rgalternates;
  2476.     sub_expr<CI>  ** m_pptail; // only used when adding elements
  2477.     size_t const     m_cgroup;
  2478.     width_type       m_nwidth;
  2479. };
  2480. template< typename CI >
  2481. inline match_group_base<CI>::~match_group_base()
  2482. {
  2483. }
  2484. // A indestructable_sub_expr is an object that brings itself back
  2485. // to life after explicitly being deleted.  It is used
  2486. // to ease clean-up of the sub_expr graph, where most
  2487. // nodes are dynamically allocated, but some nodes are
  2488. // members of other nodes and are not dynamically allocated.
  2489. // The recursive delete of the sub_expr graph causes
  2490. // delete to be ( incorrectly ) called on these members.
  2491. // By inheriting these members from indestructable_sub_expr,
  2492. // explicit attempts to delete the object will have no
  2493. // effect. ( Actually, the object will be destructed and
  2494. // then immediately reconstructed. ) This is accomplished
  2495. // by calling placement new in operator delete.
  2496. template< typename CI, typename T >
  2497. class indestructable_sub_expr : public sub_expr<CI>
  2498. {
  2499.     static void * operator new( size_t, regex_arena & );
  2500.     static void operator delete( void *, regex_arena & );
  2501. protected:
  2502.     static void * operator new( size_t, void * pv ) { return pv; }
  2503.     static void operator delete( void *, void * ) {}
  2504. public:
  2505.     virtual ~indestructable_sub_expr() {}
  2506.     static void operator delete( void * pv ) { new( pv ) T; }
  2507. };
  2508. template< typename CI >
  2509. class match_group : public match_group_base<CI>
  2510. {
  2511.     match_group & operator=( match_group const & );
  2512. public:
  2513.     match_group( size_t cgroup, regex_arena & arena )
  2514.         : match_group_base<CI>( cgroup, arena ),
  2515.           m_end_group( this ) 
  2516.     {
  2517.     }
  2518.     virtual ~match_group()
  2519.     {
  2520.         _cleanup();
  2521.     }
  2522.     virtual sub_expr<CI> * quantify( size_t lbound, size_t ubound, bool greedy, regex_arena & arena )
  2523.     {
  2524.         if( greedy )
  2525.             return new( arena ) max_group_quantifier<CI>( this, lbound, ubound );
  2526.         else
  2527.             return new( arena ) min_group_quantifier<CI>( this, lbound, ubound );
  2528.     }
  2529. protected:
  2530.     typedef typename match_group_base<CI>::alt_list_type alt_list_type;
  2531.     struct old_backref
  2532.     {
  2533.         CI   istart;
  2534.         CI   iend;
  2535.         bool matched;
  2536.         old_backref() {}
  2537.         old_backref( backref_tag<CI> const & br )
  2538.             : istart( br.first ), iend( br.second ), matched( br.matched ) {}
  2539.     };
  2540.     static void restore_backref( backref_tag<CI> & br, old_backref const & old_br )
  2541.     {
  2542.         br.first   = old_br.istart;
  2543.         br.second  = old_br.iend;
  2544.         br.matched = old_br.matched;
  2545.     }
  2546.     template< typename CSTRINGS >
  2547.     bool _call_back( match_param<CI> & param, CI icur, CSTRINGS ) const
  2548.     {
  2549.         if( size_t( -1 ) != m_cgroup )
  2550.         {
  2551.             // Save the relevant portions of the backref in an old_backref struct
  2552.             old_backref old_br( ( *param.prgbackrefs )[ m_cgroup ] );
  2553.             ( *param.prgbackrefs )[ m_cgroup ].first   = ( *param.prgbackrefs )[ m_cgroup ].reserved1;
  2554.             ( *param.prgbackrefs )[ m_cgroup ].second  = icur;
  2555.             ( *param.prgbackrefs )[ m_cgroup ].matched = true;
  2556.             if( recursive_match_next_( param, icur, CSTRINGS() ) )
  2557.                 return true;
  2558.             // Restore the backref to its saved state
  2559.             restore_backref( ( *param.prgbackrefs )[ m_cgroup ], old_br );
  2560.         }
  2561.         else
  2562.         {
  2563.             if( recursive_match_next_( param, icur, CSTRINGS() ) )
  2564.                 return true;
  2565.         }
  2566.         return false;
  2567.     }
  2568.     class end_group : public indestructable_sub_expr<CI, end_group>
  2569.     {
  2570.         match_group<CI> const *const m_pgroup;
  2571.         end_group & operator=( end_group const & );
  2572.         void _push_frame( match_param<CI> & param ) const
  2573.         {
  2574.             size_t cgroup = m_pgroup->group_number();
  2575.             if( size_t( -1 ) != cgroup )
  2576.             {
  2577.                 backref_tag<CI> & br = ( *param.prgbackrefs )[ cgroup ];
  2578.                 old_backref old_br( br );
  2579.                 param.pstack->push( old_br );
  2580.                 br.first   = br.reserved1;
  2581.                 br.second  = param.icur;
  2582.                 br.matched = true;
  2583.             }
  2584.         }
  2585.         void _pop_frame( match_param<CI> & param ) const
  2586.         {
  2587.             size_t cgroup = m_pgroup->group_number();
  2588.             if( size_t( -1 ) != cgroup )
  2589.             {
  2590.                 old_backref old_br;
  2591.                 param.pstack->pop( old_br );
  2592.                 match_group<CI>::restore_backref( ( *param.prgbackrefs )[ cgroup ], old_br );
  2593.             }
  2594.         }
  2595.         bool _iterative_match_this( match_param<CI> & param ) const
  2596.         {
  2597.             _push_frame( param );
  2598.             param.next = m_pgroup->next();
  2599.             return true;
  2600.         }
  2601.         bool _iterative_rematch_this( match_param<CI> & param ) const
  2602.         {
  2603.             _pop_frame( param );
  2604.             return false;
  2605.         }
  2606.     public:
  2607.         end_group( match_group<CI> const * pgroup = NULL )
  2608.             : m_pgroup( pgroup ) 
  2609.         {
  2610.         }
  2611.         virtual bool recursive_match_all_( match_param<CI> & param, CI icur ) const
  2612.         {
  2613.             return m_pgroup->_call_back( param, icur, false_t() );
  2614.         }
  2615.         virtual bool recursive_match_all_c( match_param<CI> & param, CI icur ) const
  2616.         {
  2617.             return m_pgroup->_call_back( param, icur, true_t() );
  2618.         }
  2619.         virtual bool iterative_match_this_( match_param<CI> & param ) const
  2620.         {
  2621.             return _iterative_match_this( param );
  2622.         }
  2623.         virtual bool iterative_match_this_c( match_param<CI> & param ) const
  2624.         {
  2625.             return _iterative_match_this( param );
  2626.         }
  2627.         virtual bool iterative_rematch_this_( match_param<CI> & param ) const
  2628.         {
  2629.             return _iterative_rematch_this( param );
  2630.         }
  2631.         virtual bool iterative_rematch_this_c( match_param<CI> & param ) const
  2632.         {
  2633.             return _iterative_rematch_this( param );
  2634.         }
  2635.         virtual width_type width_this( width_param<CI> & )
  2636.         { 
  2637.             return zero_width; 
  2638.         }
  2639.     } m_end_group;
  2640.     friend class end_group;
  2641.     virtual sub_expr<CI> * _get_end_group()
  2642.     {
  2643.         return & m_end_group;
  2644.     }
  2645. };
  2646. template< typename CI >
  2647. inline void save_backrefs( std::vector<backref_tag<CI> > const & rgbackrefs, CI * prgci )
  2648. {
  2649.     typedef typename std::vector<backref_tag<CI> >::const_iterator VI;
  2650.     for( VI iter = rgbackrefs.begin(); iter != rgbackrefs.end(); ++iter, ++prgci )
  2651.     {
  2652.         new( static_cast<void*>( prgci ) ) CI( iter->reserved1 );
  2653.     }
  2654. }
  2655. template< typename CI >
  2656. inline void restore_backrefs( std::vector<backref_tag<CI> > & rgbackrefs, CI * prgci )
  2657. {
  2658.     typedef typename std::vector<backref_tag<CI> >::iterator VI;
  2659.     for( VI iter = rgbackrefs.begin(); iter != rgbackrefs.end(); ++iter, ++prgci )
  2660.     {
  2661.         iter->reserved1 = *prgci;
  2662.         prgci->~CI();
  2663.     }
  2664. }
  2665. template< typename CI >
  2666. class group_wrapper : public sub_expr<CI>
  2667. {
  2668.     match_group_base<CI> const *const m_pgroup;
  2669.     group_wrapper & operator=( group_wrapper const & );
  2670. public:
  2671.     group_wrapper( match_group_base<CI> const * pgroup ) 
  2672.         : m_pgroup( pgroup ) 
  2673.     {
  2674.     }
  2675.     virtual bool iterative_match_this_( match_param<CI> & param ) const
  2676.     {
  2677.         return m_pgroup->match_group_base<CI>::iterative_match_this_( param );
  2678.     }
  2679.     virtual bool iterative_match_this_c( match_param<CI> & param ) const
  2680.     {
  2681.         return m_pgroup->match_group_base<CI>::iterative_match_this_c( param );
  2682.     }
  2683.     virtual bool iterative_rematch_this_( match_param<CI> & param ) const
  2684.     {