00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00026
00054
00055
00056 #ifndef _CTTL_XTL_OP_IMPL_H_INCLUDED_
00057 #define _CTTL_XTL_OP_IMPL_H_INCLUDED_
00058
00059 namespace cttl_impl {
00060
00062
00064
00075 template< typename ExprT >
00076 class xtl_op_base_unary {
00077
00078 protected:
00080 ExprT m_expr;
00081
00082 public:
00083
00084
00086 xtl_op_base_unary( ExprT const& expr_ )
00087 : m_expr( expr_ )
00088 {
00089 }
00090
00091 protected:
00115 template< typename SubstrT >
00116 size_t kleene_list( SubstrT& edge_, size_t upper_limit_ = 0 )
00117 {
00118
00119 typename SubstrT::offset_guard_T iteration_offset( edge_.first, SubstrT::string_T::npos );
00120 typename SubstrT::offset_guard_T match_offset( edge_.first, SubstrT::string_T::npos );
00121
00122
00123
00124 size_t saved_end_offset = edge_.second.offset();
00125
00126 size_t cnt = 0;
00127 while ( ( match_offset = m_expr.match( edge_ ) ) != SubstrT::string_T::npos ) {
00128
00129
00130
00131
00132
00133
00134 if ( saved_end_offset == edge_.second.offset() ) {
00135 if ( iteration_offset == edge_.first.offset() ) {
00136 CTTL_TRACE_TEXT( 'i', "kleene_list: iteration made no progress: bailing out" );
00137 break;
00138 }
00139
00140 ++cnt;
00141
00142 if ( match_offset == edge_.first.offset() ) {
00143
00144
00145 CTTL_TRACE_TEXT( 'i', "kleene_list: epsilon match: bailing out" );
00146 break;
00147 }
00148
00149 } else {
00150 ++cnt;
00151 saved_end_offset = edge_.second.offset();
00152 }
00153
00154 if ( upper_limit_ && ( cnt == upper_limit_ ) ) {
00155 CTTL_TRACE_TEXT( 'i', "kleene_list: user-specified match limit: bailing out" );
00156 break;
00157 }
00158
00159 iteration_offset = edge_.first.offset();
00160 }
00161 return cnt;
00162 }
00163
00164 private:
00166 xtl_op_base_unary< ExprT >& operator=( xtl_op_base_unary< ExprT > const& );
00167
00168 };
00169
00170
00187 template< typename Left_exprT, typename Right_exprT >
00188 class xtl_op_base_binary {
00189
00190 protected:
00192 Left_exprT m_expr_lhs;
00193
00195 Right_exprT m_expr_rhs;
00196
00197 public:
00198
00199
00200
00220 xtl_op_base_binary( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
00221 : m_expr_lhs( lhs_expr_ ), m_expr_rhs( rhs_expr_ )
00222 {
00223 }
00224
00225 private:
00227 xtl_op_base_binary< Left_exprT, Right_exprT >& operator=( xtl_op_base_binary< Left_exprT, Right_exprT > const& );
00228
00229 };
00230
00231
00233
00235
00246 template< typename ExprT >
00247 struct xtl_opunarbang : public xtl_op_base_unary< ExprT > {
00248
00249
00250
00252 xtl_opunarbang( ExprT const& expr_ )
00253 : xtl_op_base_unary< ExprT >( expr_ )
00254 {
00255 }
00256
00257
00258
00273 template< typename SubstrT >
00274 size_t match( SubstrT& edge_ )
00275 {
00276 CTTL_TRACE_LEVEL_MATCH( '!' );
00277 return this->m_expr.find( edge_ );
00278 }
00279
00295 template< typename SubstrT >
00296 size_t find( SubstrT& edge_ )
00297 {
00298 CTTL_TRACE_LEVEL_FIND( '!' );
00299 return this->m_expr.bang_find( edge_ );
00300 }
00301
00321 template< typename SubstrT >
00322 size_t bang_find( SubstrT& edge_ )
00323 {
00324 CTTL_TRACE_LEVEL_BANG( '!' );
00325 return this->m_expr.bang_find( edge_ );
00326 }
00327
00328 private:
00330 xtl_opunarbang< ExprT >& operator=( xtl_opunarbang< ExprT > const& );
00331
00332 };
00333
00334
00345 template< typename ExprT >
00346 class xtl_opunarstar : public xtl_op_base_unary< ExprT > {
00347
00348 protected:
00349
00351 size_t m_upper_limit;
00352
00353 public:
00354
00355
00365 xtl_opunarstar( ExprT const& expr_, size_t upper_limit_ = 0 )
00366 : xtl_op_base_unary< ExprT >( expr_ ), m_upper_limit( upper_limit_ )
00367 {
00368 }
00369
00370
00371
00396 template< typename SubstrT >
00397 size_t match( SubstrT& edge_ )
00398 {
00399
00400 CTTL_TRACE_LEVEL_MATCH( '*' );
00401 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
00402
00403
00404
00405 size_t saved_end_offset = edge_.second.offset();
00406 typename SubstrT::offset_guard_T match_offset( edge_.first, this->m_expr.match( edge_ ) );
00407
00408 if ( match_offset != SubstrT::string_T::npos ) {
00409
00410
00411
00412
00413
00414
00415 if ( saved_end_offset == edge_.second.offset() ) {
00416 if ( saved_first_offset == edge_.first.offset() ) {
00417
00418
00419 return match_offset;
00420 }
00421 }
00422
00423 if ( m_upper_limit ) {
00424
00425
00426
00427 if ( m_upper_limit == 1 ) {
00428
00429
00430 return match_offset;
00431 }
00432
00433
00434
00435 kleene_list( edge_, m_upper_limit - 1 );
00436
00437 } else
00438
00439 kleene_list( edge_ );
00440
00441 } else {
00442
00443
00444 return saved_first_offset;
00445 }
00446
00447 return match_offset;
00448 }
00449
00474 template< typename SubstrT >
00475 size_t find( SubstrT& edge_ )
00476 {
00477
00478 CTTL_TRACE_LEVEL_FIND( '*' );
00479 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
00480
00481
00482
00483
00484 size_t saved_end_offset = edge_.second.offset();
00485 typename SubstrT::offset_guard_T match_offset( edge_.first, this->m_expr.find( edge_ ) );
00486
00487 if ( match_offset != SubstrT::string_T::npos ) {
00488
00489
00490
00491
00492
00493 if ( saved_end_offset == edge_.second.offset() ) {
00494 if ( saved_first_offset == edge_.first.offset() ) {
00495
00496
00497 return match_offset;
00498 }
00499 }
00500
00501 if ( m_upper_limit ) {
00502
00503
00504
00505 if ( m_upper_limit == 1 ) {
00506
00507
00508 return match_offset;
00509 }
00510
00511
00512
00513 kleene_list( edge_, m_upper_limit - 1 );
00514
00515 } else
00516
00517 kleene_list( edge_ );
00518
00519 } else {
00520
00521
00522 return saved_first_offset;
00523 }
00524
00525 return match_offset;
00526 }
00527
00553 template< typename SubstrT >
00554 size_t bang_find( SubstrT& edge_ )
00555 {
00556
00557 CTTL_TRACE_LEVEL_BANG( '*' );
00558 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
00559
00560
00561
00562 size_t saved_end_offset = edge_.second.offset();
00563 typename SubstrT::offset_guard_T match_offset( edge_.first, this->m_expr.bang_find( edge_ ) );
00564
00565 if ( match_offset != SubstrT::string_T::npos ) {
00566
00567
00568
00569
00570
00571
00572 if ( saved_end_offset == edge_.second.offset() ) {
00573 if ( saved_first_offset == edge_.first.offset() ) {
00574
00575
00576 return match_offset;
00577 }
00578 }
00579
00580 if ( m_upper_limit ) {
00581
00582
00583
00584 if ( m_upper_limit == 1 ) {
00585
00586
00587 return match_offset;
00588 }
00589
00590
00591
00592 kleene_list( edge_, m_upper_limit - 1 );
00593
00594 } else
00595
00596 kleene_list( edge_ );
00597
00598 } else {
00599
00600
00601 return saved_first_offset;
00602 }
00603
00604 return match_offset;
00605 }
00606
00607 private:
00609 xtl_opunarstar< ExprT >& operator=( xtl_opunarstar< ExprT > const& );
00610
00611 };
00612
00613
00624 template< typename ExprT >
00625 class xtl_opunarminus : public xtl_op_base_unary< ExprT > {
00626
00627 public:
00628
00629
00636 xtl_opunarminus( ExprT const& expr_ )
00637 : xtl_op_base_unary< ExprT >( expr_ )
00638 {
00639 }
00640
00641
00642
00665 template< typename SubstrT >
00666 size_t match( SubstrT& edge_ )
00667 {
00668
00669 CTTL_TRACE_LEVEL_MATCH( '-' );
00670 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
00671 size_t match_offset = this->m_expr.match( edge_ );
00672
00673 if ( match_offset != SubstrT::string_T::npos ) {
00674
00675
00676 edge_.first.offset( saved_first_offset );
00677 CTTL_TRACE_RESULT( false, '-' );
00678 return SubstrT::string_T::npos;
00679 }
00680
00681
00682
00683 return saved_first_offset;
00684 }
00685
00686
00709 template< typename SubstrT >
00710 size_t find( SubstrT& edge_ )
00711 {
00712
00713 CTTL_TRACE_LEVEL_FIND( '-' );
00714 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
00715 size_t match_offset = this->m_expr.find( edge_ );
00716
00717 if ( match_offset != SubstrT::string_T::npos ) {
00718
00719
00720 edge_.first.offset( saved_first_offset );
00721 CTTL_TRACE_RESULT( false, '-' );
00722 return SubstrT::string_T::npos;
00723 }
00724
00725
00726
00727 return saved_first_offset;
00728 }
00729
00730
00754 template< typename SubstrT >
00755 size_t bang_find( SubstrT& edge_ )
00756 {
00757
00758 CTTL_TRACE_LEVEL_BANG( '-' );
00759 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
00760 size_t match_offset = this->m_expr.bang_find( edge_ );
00761
00762 if ( match_offset != SubstrT::string_T::npos ) {
00763
00764
00765 edge_.first.offset( saved_first_offset );
00766 CTTL_TRACE_RESULT( false, '-' );
00767 return SubstrT::string_T::npos;
00768 }
00769
00770
00771
00772 return saved_first_offset;
00773 }
00774
00775 };
00776
00777
00794 template< typename ExprT >
00795 class xtl_opunarplus : public xtl_op_base_unary< ExprT > {
00796
00797 protected:
00799 size_t m_upper_limit;
00800
00802 size_t m_lower_limit;
00803
00822 template< typename SubstrT >
00823 size_t unarplus( SubstrT& edge_, size_t saved_end_offset_, size_t first_match_offset_ )
00824 {
00825 typename SubstrT::offset_guard_T match_offset( edge_.first, first_match_offset_ );
00826
00827 if ( match_offset != SubstrT::string_T::npos ) {
00828
00829
00830
00831
00832
00833 if ( saved_end_offset_ == edge_.second.offset() ) {
00834 if ( match_offset == edge_.first.offset() ) {
00835
00836
00837 if ( !m_upper_limit )
00838 return match_offset;
00839
00840 if ( ( m_lower_limit <= 1 ) && ( 1 <= m_upper_limit ) )
00841 return match_offset;
00842
00843 CTTL_TRACE_TEXT_RESULT( false, '+', "kleene plus: too few matches (one epsilon found)" );
00844 return SubstrT::string_T::npos;
00845 }
00846 }
00847
00848 if ( m_upper_limit ) {
00849 if ( m_upper_limit == 1 )
00850
00851 return match_offset;
00852
00853
00854
00855 if ( m_lower_limit ) {
00856
00857
00858
00859
00860
00861
00862
00863
00864
00865
00866 size_t cnt = 0;
00867 if ( m_upper_limit == SubstrT::string_T::npos ) {
00868 if ( m_lower_limit == 1 ) {
00869
00870
00871 return match_offset;
00872 }
00873
00874 cnt = kleene_list( edge_, m_lower_limit - 1 ) + 1;
00875 } else {
00876 cnt = kleene_list( edge_, m_upper_limit ) + 1;
00877 }
00878
00879 if ( cnt > m_upper_limit ) {
00880 CTTL_TRACE_TEXT_RESULT( false, '+', "kleene plus: too many matches" );
00881 return SubstrT::string_T::npos;
00882
00883 }
00884
00885 if ( cnt < m_lower_limit ) {
00886
00887 CTTL_TRACE_TEXT_RESULT( false, '+', "kleene plus: too few matches" );
00888 return SubstrT::string_T::npos;
00889
00890 } else if ( m_upper_limit == SubstrT::string_T::npos ) {
00891
00892
00893 return match_offset;
00894 }
00895
00896 } else {
00897
00898
00899 kleene_list( edge_, m_upper_limit - 1 );
00900 }
00901
00902 } else
00903
00904
00905 kleene_list( edge_ );
00906
00907 return match_offset;
00908 }
00909
00910 CTTL_TRACE_RESULT( false, '+' );
00911 return SubstrT::string_T::npos;
00912 }
00913
00914 public:
00915
00916
00917
00930 xtl_opunarplus( ExprT const& expr_, size_t upper_limit_ = 0, size_t lower_limit_ = 0 )
00931 : xtl_op_base_unary< ExprT >( expr_ ), m_upper_limit( upper_limit_ ), m_lower_limit( lower_limit_ )
00932 {
00933 }
00934
00935
00936
00937
00963 template< typename SubstrT >
00964 size_t match( SubstrT& edge_ )
00965 {
00966
00967 CTTL_TRACE_LEVEL_MATCH( '+' );
00968 size_t saved_end_offset = edge_.second.offset();
00969 return unarplus( edge_, saved_end_offset, this->m_expr.match( edge_ ) );
00970 }
00971
00972
00998 template< typename SubstrT >
00999 size_t find( SubstrT& edge_ )
01000 {
01001
01002 CTTL_TRACE_LEVEL_FIND( '+' );
01003 size_t saved_end_offset = edge_.second.offset();
01004 return unarplus( edge_, saved_end_offset, this->m_expr.find( edge_ ) );
01005 }
01006
01007
01034 template< typename SubstrT >
01035 size_t bang_find( SubstrT& edge_ )
01036 {
01037
01038 CTTL_TRACE_LEVEL_BANG( '+' );
01039
01040
01041
01042
01043
01044 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
01045 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, SubstrT::string_T::npos );
01046
01047 typename SubstrT::offset_guard_T iteration_offset( edge_.first, SubstrT::string_T::npos );
01048
01049 while ( ( match_lhs_offset = this->m_expr.bang_find( edge_ ) ) != SubstrT::string_T::npos ) {
01050 size_t saved_end_offset = edge_.second.offset();
01051 if ( unarplus( edge_, saved_end_offset, match_lhs_offset ) != SubstrT::string_T::npos )
01052 return match_lhs_offset;
01053
01054 if ( iteration_offset == edge_.first.offset() ) {
01055 CTTL_TRACE_TEXT( '+', "!!kleene plus: search made no progress: bailing out" );
01056 break;
01057 }
01058
01059 iteration_offset = edge_.first.offset();
01060 }
01061
01062
01063 edge_.first.offset( saved_first_offset );
01064 return SubstrT::string_T::npos;
01065 }
01066
01067 private:
01069 xtl_opunarplus< ExprT >& operator=( xtl_opunarplus< ExprT > const& );
01070
01071 };
01072
01073
01085 template< typename ExprT >
01086 struct xtl_entity : public xtl_op_base_unary< ExprT > {
01087
01088
01089
01096 xtl_entity( ExprT const& expr_ )
01097 : xtl_op_base_unary< ExprT >( expr_ )
01098 {
01099 }
01100
01101
01102
01128 template< typename SubstrT >
01129 size_t match( SubstrT& edge_ )
01130 {
01131 CTTL_TRACE_LEVEL_MATCH( 'E' );
01132 typename SubstrT::offset_guard_T match_offset( edge_.first, this->m_expr.match( edge_ ) );
01133 if ( match_offset != SubstrT::string_T::npos ) {
01134 if ( match_offset != edge_.first.offset() ) {
01135 CTTL_TRACE_RESULT( true, 'E' );
01136 return match_offset;
01137 } else {
01138 CTTL_TRACE_STATIC_RESULT( false, 'E', "epsilon match rejected" );
01139 }
01140 }
01141
01142 return SubstrT::string_T::npos;
01143 }
01144
01145
01171 template< typename SubstrT >
01172 size_t find( SubstrT& edge_ )
01173 {
01174 CTTL_TRACE_LEVEL_FIND( 'E' );
01175 typename SubstrT::offset_guard_T match_offset( edge_.first, this->m_expr.find( edge_ ) );
01176 if ( ( match_offset != SubstrT::string_T::npos ) && ( match_offset != edge_.first.offset() ) )
01177 return match_offset;
01178
01179 return SubstrT::string_T::npos;
01180 }
01181
01182
01207 template< typename SubstrT >
01208 size_t bang_find( SubstrT& edge_ )
01209 {
01210 CTTL_TRACE_LEVEL_BANG( 'E' );
01211 typename SubstrT::offset_guard_T match_offset( edge_.first, this->m_expr.bang_find( edge_ ) );
01212 if ( ( match_offset != SubstrT::string_T::npos ) && ( match_offset != edge_.first.offset() ) )
01213 return match_offset;
01214
01215 return SubstrT::string_T::npos;
01216 }
01217
01218 };
01219
01220
01232 template< typename ExprT >
01233 struct xtl_lookahead : public xtl_op_base_unary< ExprT > {
01234
01235
01236
01243 xtl_lookahead( ExprT const& expr_ )
01244 : xtl_op_base_unary< ExprT >( expr_ )
01245 {
01246 }
01247
01248
01249
01276 template< typename SubstrT >
01277 size_t match( SubstrT& edge_ )
01278 {
01279 CTTL_TRACE_LEVEL_MATCH( 'A' );
01280 typedef
01281 xtl_node<
01282 typename SubstrT::node_T,
01283 xtl_wrap< ExprT >
01284 > xtl_node_T;
01285
01286 return xtl_wrap< xtl_node_T >( xtl_node_T( edge_.first, this->m_expr ) ).match( edge_ );
01287 }
01288
01289
01316 template< typename SubstrT >
01317 size_t find( SubstrT& edge_ )
01318 {
01319 CTTL_TRACE_LEVEL_FIND( 'A' );
01320 typedef
01321 xtl_node<
01322 typename SubstrT::node_T,
01323 xtl_wrap< ExprT >
01324 > xtl_node_T;
01325
01326 return xtl_wrap< xtl_node_T >( xtl_node_T( edge_.first, this->m_expr ) ).find( edge_ );
01327 }
01328
01329
01356 template< typename SubstrT >
01357 size_t bang_find( SubstrT& edge_ )
01358 {
01359 CTTL_TRACE_LEVEL_BANG( 'A' );
01360 typedef
01361 xtl_node<
01362 typename SubstrT::node_T,
01363 xtl_wrap< ExprT >
01364 > xtl_node_T;
01365
01366 return xtl_wrap< xtl_node_T >( xtl_node_T( edge_.first, this->m_expr ) ).bang_find( edge_ );
01367 }
01368
01369 };
01370
01371
01373
01375
01392 template< typename Left_exprT, typename Right_exprT >
01393 struct xtl_opbinplus : public xtl_op_base_binary< Left_exprT, Right_exprT > {
01394
01395
01396
01416 xtl_opbinplus( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
01417 : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
01418 {
01419 }
01420
01421
01422
01447 template< typename SubstrT >
01448 size_t match( SubstrT& edge_ )
01449 {
01450
01451
01452 CTTL_TRACE_LEVEL_MATCH( ';' );
01453 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
01454 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.match( edge_ ) );
01455
01456 if (
01457 ( match_lhs_offset != SubstrT::string_T::npos )
01458 &&
01459 ( this->m_expr_rhs.match( edge_ ) != SubstrT::string_T::npos )
01460 )
01461 return match_lhs_offset;
01462
01463
01464 edge_.first.offset( saved_first_offset );
01465 return SubstrT::string_T::npos;
01466 }
01467
01468
01493 template< typename SubstrT >
01494 size_t find( SubstrT& edge_ )
01495 {
01496
01497 CTTL_TRACE_LEVEL_FIND( ';' );
01498 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
01499 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.find( edge_ ) );
01500
01501 if (
01502 ( match_lhs_offset != SubstrT::string_T::npos )
01503 &&
01504 ( this->m_expr_rhs.match( edge_ ) != SubstrT::string_T::npos )
01505 )
01506 return match_lhs_offset;
01507
01508 edge_.first.offset( saved_first_offset );
01509 return SubstrT::string_T::npos;
01510 }
01511
01512
01537 template< typename SubstrT >
01538 size_t bang_find( SubstrT& edge_ )
01539 {
01540
01541 CTTL_TRACE_LEVEL_BANG( ';' );
01542 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
01543 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, SubstrT::string_T::npos );
01544
01545 typename SubstrT::offset_guard_T iteration_offset( edge_.first, SubstrT::string_T::npos );
01546
01547 while ( ( match_lhs_offset = this->m_expr_lhs.bang_find( edge_ ) ) != SubstrT::string_T::npos ) {
01548 if ( this->m_expr_rhs.match( edge_ ) != SubstrT::string_T::npos )
01549 return match_lhs_offset;
01550
01551 if ( iteration_offset == edge_.first.offset() ) {
01552 CTTL_TRACE_TEXT( ';', "!!(R1+R2): search made no progress: bailing out" );
01553 break;
01554 }
01555
01556 iteration_offset = edge_.first.offset();
01557 }
01558
01559
01560 edge_.first.offset( saved_first_offset );
01561 return SubstrT::string_T::npos;
01562 }
01563
01564 private:
01566 xtl_opbinplus< Left_exprT, Right_exprT >& operator=( xtl_opbinplus< Left_exprT, Right_exprT > const& );
01567
01568 };
01569
01570
01587 template< typename Left_exprT, typename Right_exprT >
01588 struct xtl_opbinpipe : public xtl_op_base_binary< Left_exprT, Right_exprT > {
01589
01590
01591
01592
01612 xtl_opbinpipe( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
01613 : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
01614 {
01615 }
01616
01617
01618
01644 template< typename SubstrT >
01645 size_t match( SubstrT& edge_ )
01646 {
01647
01648
01649 CTTL_TRACE_LEVEL_MATCH( '|' );
01650 size_t match_offset = this->m_expr_lhs.match( edge_ );
01651 if ( match_offset != SubstrT::string_T::npos )
01652 return match_offset;
01653
01654 match_offset = this->m_expr_rhs.match( edge_ );
01655 if ( match_offset != SubstrT::string_T::npos )
01656 return match_offset;
01657
01658 CTTL_TRACE_RESULT( false, '|' );
01659 return SubstrT::string_T::npos;
01660 }
01661
01662
01687 template< typename SubstrT >
01688 size_t find( SubstrT& edge_ )
01689 {
01690
01691
01692 CTTL_TRACE_LEVEL_FIND( '|' );
01693 size_t match_offset = this->m_expr_lhs.find( edge_ );
01694 if ( match_offset != SubstrT::string_T::npos )
01695 return match_offset;
01696
01697 match_offset = this->m_expr_rhs.find( edge_ );
01698 if ( match_offset != SubstrT::string_T::npos )
01699 return match_offset;
01700
01701 CTTL_TRACE_RESULT( false, '|' );
01702 return SubstrT::string_T::npos;
01703 }
01704
01705
01731 template< typename SubstrT >
01732 size_t bang_find( SubstrT& edge_ )
01733 {
01734
01735
01736 CTTL_TRACE_LEVEL_BANG( '|' );
01737 size_t match_offset = this->m_expr_lhs.bang_find( edge_ );
01738 if ( match_offset != SubstrT::string_T::npos )
01739 return match_offset;
01740
01741 match_offset = this->m_expr_rhs.bang_find( edge_ );
01742 if ( match_offset != SubstrT::string_T::npos )
01743 return match_offset;
01744
01745 CTTL_TRACE_RESULT( false, '|' );
01746 return SubstrT::string_T::npos;
01747 }
01748
01749 private:
01751 xtl_opbinpipe< Left_exprT, Right_exprT >& operator=( xtl_opbinpipe< Left_exprT, Right_exprT > const& );
01752
01753 };
01754
01755
01772 template< typename Left_exprT, typename Right_exprT >
01773 struct xtl_opbin2pipe : public xtl_op_base_binary< Left_exprT, Right_exprT > {
01774
01775
01776
01796 xtl_opbin2pipe( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
01797 : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
01798 {
01799 }
01800
01801
01802
01828 template< typename SubstrT >
01829 size_t match( SubstrT& edge_ )
01830 {
01831
01832
01833 CTTL_TRACE_LEVEL_MATCH( '|' );
01834
01835 xtl_edge_offset_guard< SubstrT > saved_lhs_edge( edge_ );
01836
01837
01838 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.match( edge_ ) );
01839 if ( match_lhs_offset != SubstrT::string_T::npos )
01840
01841
01842 saved_lhs_edge.swap( edge_ );
01843
01844
01845 typename SubstrT::offset_guard_T match_rhs_offset( edge_.first, this->m_expr_rhs.match( edge_ ) );
01846 if ( match_rhs_offset != SubstrT::string_T::npos ) {
01847
01848 if ( match_lhs_offset == SubstrT::string_T::npos )
01849
01850 return match_rhs_offset;
01851
01852
01853
01854 if (
01855 ( match_lhs_offset == match_rhs_offset )
01856 &&
01857 ( saved_lhs_edge.first - match_lhs_offset < edge_.first.offset() - match_rhs_offset )
01858 )
01859
01860 return match_rhs_offset;
01861
01862
01863 else if ( match_rhs_offset < match_lhs_offset )
01864
01865 return match_rhs_offset;
01866
01867
01868 }
01869
01870 if ( match_lhs_offset != SubstrT::string_T::npos ) {
01871
01872
01873 saved_lhs_edge.restore( edge_ );
01874 return match_lhs_offset;
01875 }
01876
01877
01878
01879 CTTL_TRACE_TEXT_RESULT( false, '|', "||" );
01880 return SubstrT::string_T::npos;
01881 }
01882
01883
01909 template< typename SubstrT >
01910 size_t find( SubstrT& edge_ )
01911 {
01912
01913
01914 CTTL_TRACE_LEVEL_FIND( '|' );
01915
01916 xtl_edge_offset_guard< SubstrT > saved_lhs_edge( edge_ );
01917
01918
01919 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.find( edge_ ) );
01920 if ( match_lhs_offset != SubstrT::string_T::npos )
01921
01922
01923 saved_lhs_edge.swap( edge_ );
01924
01925
01926 typename SubstrT::offset_guard_T match_rhs_offset( edge_.first, this->m_expr_rhs.find( edge_ ) );
01927 if ( match_rhs_offset != SubstrT::string_T::npos ) {
01928
01929 if ( match_lhs_offset == SubstrT::string_T::npos )
01930
01931 return match_rhs_offset;
01932
01933
01934
01935 if (
01936 ( match_lhs_offset == match_rhs_offset )
01937 &&
01938 ( saved_lhs_edge.first - match_lhs_offset < edge_.first.offset() - match_rhs_offset )
01939 )
01940
01941 return match_rhs_offset;
01942
01943
01944 else if ( match_rhs_offset < match_lhs_offset )
01945
01946 return match_rhs_offset;
01947
01948
01949
01950 }
01951
01952 if ( match_lhs_offset != SubstrT::string_T::npos ) {
01953
01954
01955 saved_lhs_edge.restore( edge_ );
01956 return match_lhs_offset;
01957 }
01958
01959
01960
01961 CTTL_TRACE_TEXT_RESULT( false, '|', "||" );
01962 return SubstrT::string_T::npos;
01963
01964 }
01965
01966
01992 template< typename SubstrT >
01993 size_t bang_find( SubstrT& edge_ )
01994 {
01995
01996
01997 CTTL_TRACE_LEVEL_BANG( '|' );
01998 xtl_edge_offset_guard< SubstrT > saved_lhs_edge( edge_ );
01999
02000
02001 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.bang_find( edge_ ) );
02002 if ( match_lhs_offset != SubstrT::string_T::npos )
02003
02004
02005 saved_lhs_edge.swap( edge_ );
02006
02007
02008 typename SubstrT::offset_guard_T match_rhs_offset( edge_.first, this->m_expr_rhs.bang_find( edge_ ) );
02009 if ( match_rhs_offset != SubstrT::string_T::npos ) {
02010
02011 if ( match_lhs_offset == SubstrT::string_T::npos )
02012
02013 return match_rhs_offset;
02014
02015
02016
02017 if (
02018 ( match_lhs_offset == match_rhs_offset )
02019 &&
02020 ( saved_lhs_edge.first - match_lhs_offset < edge_.first.offset() - match_rhs_offset )
02021 )
02022
02023 return match_rhs_offset;
02024
02025
02026 else if ( match_rhs_offset < match_lhs_offset )
02027
02028 return match_rhs_offset;
02029
02030
02031
02032 }
02033
02034 if ( match_lhs_offset != SubstrT::string_T::npos ) {
02035
02036
02037 saved_lhs_edge.restore( edge_ );
02038 return match_lhs_offset;
02039 }
02040
02041
02042
02043 CTTL_TRACE_TEXT_RESULT( false, '|', "||" );
02044 return SubstrT::string_T::npos;
02045
02046 }
02047
02048 };
02049
02050
02067 template< typename Left_exprT, typename Right_exprT >
02068 struct xtl_opbinconcat : public xtl_op_base_binary< Left_exprT, Right_exprT > {
02069
02070
02071
02091 xtl_opbinconcat( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
02092 : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
02093 {
02094 }
02095
02096
02097
02098
02124 template< typename SubstrT >
02125 size_t match( SubstrT& edge_ )
02126 {
02127
02128
02129 CTTL_TRACE_LEVEL_MATCH( '^' );
02130 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
02131
02132 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.match( edge_ ) );
02133
02134 if ( match_lhs_offset != SubstrT::string_T::npos ) {
02135 typename SubstrT::strict_edge_T strict_universe( edge_ );
02136 typename SubstrT::offset_guard_T unadjusted_first_offset( edge_.first );
02137 if ( this->m_expr_rhs.match( strict_universe ) != SubstrT::string_T::npos ) {
02138
02139
02140 if ( unadjusted_first_offset == edge_.first.offset() ) {
02141
02142
02143 edge_.first = strict_universe.first.offset();
02144 }
02145 edge_.second = strict_universe.second.offset();
02146 return match_lhs_offset;
02147 }
02148 }
02149
02150 edge_.first.offset( saved_first_offset );
02151 CTTL_TRACE_RESULT( false, '^' );
02152 return SubstrT::string_T::npos;
02153 }
02154
02155
02181 template< typename SubstrT >
02182 size_t find( SubstrT& edge_ )
02183 {
02184
02185 CTTL_TRACE_LEVEL_FIND( '^' );
02186 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
02187
02188 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.find( edge_ ) );
02189
02190 if ( match_lhs_offset != SubstrT::string_T::npos ) {
02191 typename SubstrT::strict_edge_T strict_universe( edge_ );
02192 typename SubstrT::offset_guard_T unadjusted_first_offset( edge_.first );
02193 if ( this->m_expr_rhs.match( strict_universe ) != SubstrT::string_T::npos ) {
02194
02195
02196 if ( unadjusted_first_offset == edge_.first.offset() ) {
02197
02198
02199 edge_.first = strict_universe.first.offset();
02200 }
02201 edge_.second = strict_universe.second.offset();
02202 return match_lhs_offset;
02203 }
02204 }
02205
02206 edge_.first.offset( saved_first_offset );
02207 CTTL_TRACE_RESULT( false, '^' );
02208 return SubstrT::string_T::npos;
02209 }
02210
02211
02237 template< typename SubstrT >
02238 size_t bang_find( SubstrT& edge_ )
02239 {
02240
02241 CTTL_TRACE_LEVEL_BANG( '^' );
02242 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
02243 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, SubstrT::string_T::npos );
02244
02245 typename SubstrT::offset_guard_T iteration_offset( edge_.first, SubstrT::string_T::npos );
02246
02247 while ( ( match_lhs_offset = this->m_expr_lhs.bang_find( edge_ ) ) != SubstrT::string_T::npos ) {
02248 typename SubstrT::strict_edge_T strict_universe( edge_ );
02249 typename SubstrT::offset_guard_T unadjusted_first_offset( edge_.first );
02250 if ( this->m_expr_rhs.match( strict_universe ) != SubstrT::string_T::npos ) {
02251
02252
02253 if ( unadjusted_first_offset == edge_.first.offset() ) {
02254
02255
02256 edge_.first = strict_universe.first.offset();
02257 }
02258 edge_.second = strict_universe.second.offset();
02259 return match_lhs_offset;
02260 }
02261
02262 if ( iteration_offset == edge_.first.offset() ) {
02263 CTTL_TRACE_TEXT( '^', "!!(R1^R2): search made no progress: bailing out" );
02264 break;
02265 }
02266
02267 iteration_offset = edge_.first.offset();
02268 }
02269
02270 edge_.first.offset( saved_first_offset );
02271 CTTL_TRACE_RESULT( false, '^' );
02272 return SubstrT::string_T::npos;
02273 }
02274
02275 private:
02277 xtl_opbinconcat< Left_exprT, Right_exprT >& operator=( xtl_opbinconcat< Left_exprT, Right_exprT > const& );
02278
02279 };
02280
02281
02298 template< typename Left_exprT, typename Right_exprT >
02299 struct xtl_opbinminus : public xtl_op_base_binary< Left_exprT, Right_exprT > {
02300
02301
02302
02322 xtl_opbinminus( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
02323 : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
02324 {
02325 }
02326
02327
02328
02329
02355 template< typename SubstrT >
02356 size_t match( SubstrT& edge_ )
02357 {
02358
02359
02360 CTTL_TRACE_LEVEL_MATCH( '-' );
02361 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
02362 xtl_edge_offset_guard< SubstrT > saved_lhs_edge( edge_ );
02363
02364
02365 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.match( edge_ ) );
02366 if ( match_lhs_offset != SubstrT::string_T::npos ) {
02367 saved_lhs_edge.save( edge_ );
02368 edge_.second.offset( edge_.first.offset() );
02369 edge_.first.offset( match_lhs_offset );
02370 typename SubstrT::strict_edge_T strict_universe( edge_ );
02371 if ( this->m_expr_rhs.match( strict_universe ) == SubstrT::string_T::npos ) {
02372
02373 saved_lhs_edge.restore( edge_ );
02374 return match_lhs_offset;
02375 }
02376 }
02377
02378
02379 edge_.first.offset( saved_first_offset );
02380 edge_.second.offset( saved_lhs_edge.second );
02381 CTTL_TRACE_RESULT( false, '-' );
02382 return SubstrT::string_T::npos;
02383 }
02384
02385
02411 template< typename SubstrT >
02412 size_t find( SubstrT& edge_ )
02413 {
02414
02415 CTTL_TRACE_LEVEL_FIND( '-' );
02416 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
02417 xtl_edge_offset_guard< SubstrT > saved_lhs_edge( edge_ );
02418
02419
02420 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.find( edge_ ) );
02421 if ( match_lhs_offset != SubstrT::string_T::npos ) {
02422 saved_lhs_edge.save( edge_ );
02423 edge_.second.offset( edge_.first.offset() );
02424 edge_.first.offset( match_lhs_offset );
02425 typename SubstrT::strict_edge_T strict_universe( edge_ );
02426 if ( this->m_expr_rhs.match( strict_universe ) == SubstrT::string_T::npos ) {
02427
02428 saved_lhs_edge.restore( edge_ );
02429 return match_lhs_offset;
02430 }
02431 }
02432
02433
02434 edge_.first.offset( saved_first_offset );
02435 edge_.second.offset( saved_lhs_edge.second );
02436 CTTL_TRACE_RESULT( false, '-' );
02437 return SubstrT::string_T::npos;
02438 }
02439
02440
02466 template< typename SubstrT >
02467 size_t bang_find( SubstrT& edge_ )
02468 {
02469
02470 CTTL_TRACE_LEVEL_BANG( '-' );
02471 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
02472 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, SubstrT::string_T::npos );
02473 xtl_edge_offset_guard< SubstrT > saved_lhs_edge( edge_ );
02474
02475 typename SubstrT::offset_guard_T iteration_offset( edge_.first, SubstrT::string_T::npos );
02476
02477 while ( ( match_lhs_offset = this->m_expr_lhs.bang_find( edge_ ) ) != SubstrT::string_T::npos ) {
02478 saved_lhs_edge.save( edge_ );
02479 edge_.second.offset( edge_.first.offset() );
02480 edge_.first.offset( match_lhs_offset );
02481 typename SubstrT::strict_edge_T strict_universe( edge_ );
02482 if ( this->m_expr_rhs.match( strict_universe ) == SubstrT::string_T::npos ) {
02483
02484 saved_lhs_edge.restore( edge_ );
02485 return match_lhs_offset;
02486 }
02487
02488
02489 saved_lhs_edge.restore( edge_ );
02490
02491 if ( iteration_offset == edge_.first.offset() ) {
02492 CTTL_TRACE_TEXT( '-', "!!(R1-R2): search made no progress: bailing out" );
02493 break;
02494 }
02495
02496 iteration_offset = edge_.first.offset();
02497 }
02498
02499 edge_.first.offset( saved_first_offset );
02500 CTTL_TRACE_RESULT( false, '-' );
02501 return SubstrT::string_T::npos;
02502 }
02503
02504 };
02505
02506
02523 template< typename Left_exprT, typename Right_exprT >
02524 struct xtl_opbinand : public xtl_op_base_binary< Left_exprT, Right_exprT > {
02525
02526
02527
02547 xtl_opbinand( Left_exprT const& lhs_expr_, Right_exprT const& rhs_expr_ )
02548 : xtl_op_base_binary< Left_exprT, Right_exprT >( lhs_expr_, rhs_expr_ )
02549 {
02550 }
02551
02552
02553
02554
02580 template< typename SubstrT >
02581 size_t match( SubstrT& edge_ )
02582 {
02583
02584
02585 CTTL_TRACE_LEVEL_MATCH( '&' );
02586 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
02587 xtl_edge_offset_guard< SubstrT > saved_lhs_edge( edge_ );
02588
02589
02590 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.match( edge_ ) );
02591 if ( match_lhs_offset != SubstrT::string_T::npos ) {
02592 saved_lhs_edge.save( edge_ );
02593 edge_.second.offset( edge_.first.offset() );
02594 edge_.first.offset( match_lhs_offset );
02595 typename SubstrT::strict_edge_T strict_universe( edge_ );
02596 if ( this->m_expr_rhs.match( strict_universe ) != SubstrT::string_T::npos ) {
02597
02598 saved_lhs_edge.restore( edge_ );
02599 return match_lhs_offset;
02600 }
02601 }
02602
02603 edge_.first.offset( saved_first_offset );
02604 edge_.second.offset( saved_lhs_edge.second );
02605 CTTL_TRACE_RESULT( false, '&' );
02606 return SubstrT::string_T::npos;
02607 }
02608
02609
02635 template< typename SubstrT >
02636 size_t find( SubstrT& edge_ )
02637 {
02638
02639 CTTL_TRACE_LEVEL_FIND( '&' );
02640 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
02641 xtl_edge_offset_guard< SubstrT > saved_lhs_edge( edge_ );
02642
02643
02644 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, this->m_expr_lhs.find( edge_ ) );
02645 if ( match_lhs_offset != SubstrT::string_T::npos ) {
02646 saved_lhs_edge.save( edge_ );
02647 edge_.second.offset( edge_.first.offset() );
02648 edge_.first.offset( match_lhs_offset );
02649 typename SubstrT::strict_edge_T strict_universe( edge_ );
02650 if ( this->m_expr_rhs.match( strict_universe ) != SubstrT::string_T::npos ) {
02651
02652 saved_lhs_edge.restore( edge_ );
02653 return match_lhs_offset;
02654 }
02655 }
02656
02657 edge_.first.offset( saved_first_offset );
02658 edge_.second.offset( saved_lhs_edge.second );
02659 CTTL_TRACE_RESULT( false, '&' );
02660 return SubstrT::string_T::npos;
02661 }
02662
02663
02689 template< typename SubstrT >
02690 size_t bang_find( SubstrT& edge_ )
02691 {
02692
02693 CTTL_TRACE_LEVEL_BANG( '&' );
02694 typename SubstrT::offset_guard_T saved_first_offset( edge_.first );
02695 xtl_edge_offset_guard< SubstrT > saved_lhs_edge( edge_ );
02696
02697 typename SubstrT::offset_guard_T iteration_offset( edge_.first, SubstrT::string_T::npos );
02698
02699 typename SubstrT::offset_guard_T match_lhs_offset( edge_.first, SubstrT::string_T::npos );
02700 while ( ( match_lhs_offset = this->m_expr_lhs.bang_find( edge_ ) ) != SubstrT::string_T::npos ) {
02701 saved_lhs_edge.save( edge_ );
02702 edge_.second.offset( edge_.first.offset() );
02703 edge_.first.offset( match_lhs_offset );
02704 typename SubstrT::strict_edge_T strict_universe( edge_ );
02705 if ( this->m_expr_rhs.match( strict_universe ) != SubstrT::string_T::npos ) {
02706
02707 saved_lhs_edge.restore( edge_ );
02708 return match_lhs_offset;
02709 }
02710
02711
02712 saved_lhs_edge.restore( edge_ );
02713
02714 if ( iteration_offset == edge_.first.offset() ) {
02715 CTTL_TRACE_TEXT( '&', "!!(R1&R2): search made no progress: bailing out" );
02716 break;
02717 }
02718
02719 iteration_offset = edge_.first.offset();
02720 }
02721
02722 edge_.first.offset( saved_first_offset );
02723 CTTL_TRACE_RESULT( false, '&' );
02724 return SubstrT::string_T::npos;
02725 }
02726
02727 private:
02729 xtl_opbinand< Left_exprT, Right_exprT >& operator=( xtl_opbinand< Left_exprT, Right_exprT > const& );
02730
02731 };
02732
02734
02736
02738 typedef xtl_wrap< xtl_opbinplus< relaxed_bool_T, xtl_wrap< xtl_opunarbang< xtl_wrap< xtl_position_eof > > > > >
02739 universe_T;
02740
02741 }
02742
02743 #endif // _CTTL_XTL_OP_IMPL_H_INCLUDED_