boost/boost/re_detail/regex_match.hpp

   1 /*
   2  *
   3  * Copyright (c) 1998-2000
   4  * Dr John Maddock
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Dr John Maddock makes no representations
  11  * about the suitability of this software for any purpose.
  12  * It is provided "as is" without express or implied warranty.
  13  *
  14  */
  15
  16  /*
  17   *   LOCATION:    see http://www.boost.org for most recent version.
  18   *   FILE         regex_match.hpp
  19   *   VERSION      3.03
  20   *   DESCRIPTION: Regular expression matching algorithms.
  21   *                Note this is an internal header file included
  22   *                by regex.hpp, do not include on its own.
  23   */
  24
  25
  26 #ifndef BOOST_REGEX_MATCH_HPP
  27 #define BOOST_REGEX_MATCH_HPP
  28
  29
  30 namespace boost{
  31    namespace re_detail{
  32
  33 #ifdef __BORLANDC__
  34    #if __BORLANDC__ == 0x530
  35     #pragma option push -a4 -b -Ve
  36    #elif __BORLANDC__ > 0x530
  37     #pragma option push -a8 -b -Ve
  38    #endif
  39 #endif
  40
  41 template <class iterator, class charT, class traits_type, class Allocator>
  42 iterator BOOST_RE_CALL re_is_set_member(iterator next,
  43                           iterator last,
  44                           re_set_long* set_,
  45                           const reg_expression<charT, traits_type, Allocator>& e)
  46 {
  47    const charT* p = (const charT*)(set_+1);
  48    iterator ptr;
  49    unsigned int i;
  50    bool icase = e.flags() & regbase::icase;
  51
  52    if(next == last) return next;
  53
  54    typedef typename traits_type::string_type traits_string_type;
  55    const traits_type& traits_inst = e.get_traits();
  56
  57    // dwa 9/13/00 suppress incorrect MSVC warning - it claims this is never
  58    // referenced
  59    (void)traits_inst;
  60
  61    // try and match a single character, could be a multi-character
  62    // collating element...
  63    for(i = 0; i < set_->csingles; ++i)
  64    {
  65       ptr = next;
  66       if(*p == 0)
  67       {
  68          // treat null string as special case:
  69          if(traits_inst.translate(*ptr, icase) != *p)
  70          {
  71             while(*p == 0)++p;
  72             continue;
  73          }
  74          return set_->isnot ? next : (ptr == next) ? ++next : ptr;
  75       }
  76       else
  77       {
  78          while(*p && (ptr != last))
  79          {
  80             if(traits_inst.translate(*ptr, icase) != *p)
  81                break;
  82             ++p;
  83             ++ptr;
  84          }
  85
  86          if(*p == 0) // if null we've matched
  87             return set_->isnot ? next : (ptr == next) ? ++next : ptr;
  88
  89          while(*p)++p;
  90          ++p;     // skip null
  91       }
  92    }
  93
  94    charT col = traits_inst.translate(*next, icase);
  95
  96
  97    if(set_->cranges || set_->cequivalents)
  98    {
  99       traits_string_type s2(1, col);
 100       traits_string_type s1;
 101       //
 102       // try and match a range, NB only a single character can match
 103       if(set_->cranges)
 104       {
 105          if(e.flags() & regbase::nocollate)
 106             s1 = s2;
 107          else
 108             traits_inst.transform(s1, s2);
 109          for(i = 0; i < set_->cranges; ++i)
 110          {
 111             if(s1 <= p)
 112             {
 113                while(*p)++p;
 114                ++p;
 115                if(s1 >= p)
 116                   return set_->isnot ? next : ++next;
 117             }
 118             else
 119             {
 120                // skip first string
 121                while(*p)++p;
 122                ++p;
 123             }
 124             // skip second string
 125             while(*p)++p;
 126             ++p;
 127          }
 128       }
 129       //
 130       // try and match an equivalence class, NB only a single character can match
 131       if(set_->cequivalents)
 132       {
 133          traits_inst.transform_primary(s1, s2);
 134          for(i = 0; i < set_->cequivalents; ++i)
 135          {
 136             if(s1 == p)
 137                return set_->isnot ? next : ++next;
 138             // skip string
 139             while(*p)++p;
 140             ++p;
 141          }
 142       }
 143    }
 144    if(traits_inst.is_class(col, set_->cclasses) == true)
 145       return set_->isnot ? next : ++next;
 146    return set_->isnot ? ++next : next;
 147 }
 148
 149 template <class iterator, class Allocator>
 150 class _priv_match_data
 151 {
 152 public:
 153    typedef BOOST_RE_MAYBE_TYPENAME REBIND_TYPE(int, Allocator) i_alloc;
 154    typedef BOOST_RE_MAYBE_TYPENAME REBIND_TYPE(iterator, Allocator) it_alloc;
 155
 156    match_results_base<iterator, Allocator> temp_match;
 157    // failure stacks:
 158    jstack<match_results_base<iterator, Allocator>, Allocator> matches;
 159    jstack<iterator, Allocator> prev_pos;
 160    jstack<const re_syntax_base*, Allocator> prev_record;
 161    jstack<int, Allocator> prev_acc;
 162    int* accumulators;
 163    unsigned int caccumulators;
 164    iterator* loop_starts;
 165
 166    _priv_match_data(const match_results_base<iterator, Allocator>&);
 167
 168    ~_priv_match_data()
 169    {
 170       free();
 171    }
 172    void free();
 173    void set_accumulator_size(unsigned int size);
 174    int* get_accumulators()
 175    {
 176       return accumulators;
 177    }
 178    iterator* get_loop_starts()
 179    {
 180       return loop_starts;
 181    }
 182 };
 183
 184 template <class iterator, class Allocator>
 185 _priv_match_data<iterator, Allocator>::_priv_match_data(const match_results_base<iterator, Allocator>& m)
 186   : temp_match(m), matches(64, m.allocator()), prev_pos(64, m.allocator()), prev_record(64, m.allocator())
 187 {
 188   accumulators = 0;
 189   caccumulators = 0;
 190   loop_starts = 0;
 191 }
 192
 193 template <class iterator, class Allocator>
 194 void _priv_match_data<iterator, Allocator>::set_accumulator_size(unsigned int size)
 195 {
 196    if(size > caccumulators)
 197    {
 198       free();
 199       caccumulators = size;
 200       accumulators = i_alloc(temp_match.allocator()).allocate(caccumulators);
 201       loop_starts = it_alloc(temp_match.allocator()).allocate(caccumulators);
 202       for(unsigned i = 0; i < caccumulators; ++i)
 203          new (loop_starts + i) iterator();
 204    }
 205 }
 206
 207 template <class iterator, class Allocator>
 208 void _priv_match_data<iterator, Allocator>::free()
 209 {
 210    if(caccumulators)
 211    {
 212       //REBIND_INSTANCE(int, Allocator, temp_match.allocator()).deallocate(accumulators, caccumulators);
 213       i_alloc temp1(temp_match.allocator());
 214       temp1.deallocate(accumulators, caccumulators);
 215       for(unsigned i = 0; i < caccumulators; ++i)
 216          jm_destroy(loop_starts + i);
 217       //REBIND_INSTANCE(iterator, Allocator, temp_match.allocator()).deallocate(loop_starts, caccumulators);
 218       it_alloc temp2(temp_match.allocator());
 219       temp2.deallocate(loop_starts, caccumulators);
 220    }
 221 }
 222
 223 template <class charT, class traits, class Allocator>
 224 struct access_t : public reg_expression<charT, traits, Allocator>
 225 {
 226    typedef typename is_byte<charT>::width_type width_type;
 227    typedef reg_expression<charT, traits, Allocator> base_type;
 228    typedef charT char_type;
 229    typedef traits traits_type;
 230    typedef Allocator alloc_type;
 231
 232    static int repeat_count(const base_type& b)
 233    { return base_type::repeat_count(b); }
 234    static unsigned int restart_type(const base_type& b)
 235    { return base_type::restart_type(b); }
 236    static const re_syntax_base* first(const base_type& b)
 237    { return base_type::first(b); }
 238    static const unsigned char* get_map(const base_type& b)
 239    { return base_type::get_map(b); }
 240    static unsigned int leading_length(const base_type& b)
 241    { return base_type::leading_length(b); }
 242    static const kmp_info<charT>* get_kmp(const base_type& b)
 243    { return base_type::get_kmp(b); }
 244    static bool can_start(char_type c, const unsigned char* _map, unsigned char mask)
 245    {
 246       return reg_expression<char_type, traits_type, alloc_type>::can_start(c, _map, mask, width_type());
 247    }
 248 };
 249
 250
 251 #if defined(BOOST_RE_NO_TEMPLATE_SWITCH_MERGE) && !defined(BOOST_RE_NO_NAMESPACES)
 252 //
 253 // Ugly ugly hack,
 254 // template don't merge if they contain switch statements so declare these
 255 // templates in unnamed namespace (ie with internal linkage), each translation
 256 // unit then gets its own local copy, it works seemlessly but bloats the app.
 257 namespace{
 258 #endif
 259
 260 template <class iterator, class Allocator, class charT, class traits, class Allocator2>
 261 bool query_match_aux(iterator first,
 262                      iterator last,
 263                      match_results<iterator, Allocator>& m,
 264                      const reg_expression<charT, traits, Allocator2>& e,
 265                      unsigned flags,
 266                      _priv_match_data<iterator, Allocator>& pd,
 267                      iterator* restart)
 268 {
 269    typedef access_t<charT, traits, Allocator2> access;
 270
 271    if(e.flags() & regbase::failbit)
 272       return false;
 273
 274    typedef typename traits::size_type traits_size_type;
 275    typedef typename traits::uchar_type traits_uchar_type;
 276    typedef typename is_byte<charT>::width_type width_type;
 277
 278    // declare some local aliases to reduce pointer loads
 279    // good optimising compilers should make this unnecessary!!
 280    jstack<match_results_base<iterator, Allocator>, Allocator>& matches = pd.matches;
 281    jstack<iterator, Allocator>& prev_pos = pd.prev_pos;
 282    jstack<const re_syntax_base*, Allocator>& prev_record = pd.prev_record;
 283    jstack<int, Allocator>& prev_acc = pd.prev_acc;
 284    match_results_base<iterator, Allocator>& temp_match = pd.temp_match;
 285    temp_match.set_first(first);
 286
 287    const re_syntax_base* ptr = access::first(e);
 288    bool match_found = false;
 289    bool have_partial_match = false;
 290    bool need_push_match = (e.mark_count() > 1);
 291    int cur_acc = -1;    // no active accumulator
 292    pd.set_accumulator_size(access::repeat_count(e));
 293    int* accumulators = pd.get_accumulators();
 294    iterator* start_loop = pd.get_loop_starts();
 295    int k; // for loops
 296    bool icase = e.flags() & regbase::icase;
 297    *restart = first;
 298    iterator base = first;
 299    const traits& traits_inst = e.get_traits();
 300    // dwa 9/13/00 suppress incorrect MSVC warning - it claims this is never
 301    // referenced
 302    (void)traits_inst;
 303
 304    // prepare m for failure:
 305    /*
 306    if((flags & match_init) == 0)
 307    {
 308       m.init_fail(first, last);
 309    } */
 310
 311    retry:
 312
 313    while(first != last)
 314    {
 315       jm_assert(ptr);
 316       switch(ptr->type)
 317       {
 318       case syntax_element_match:
 319          match_jump:
 320          {
 321             // match found, save then fallback in case we missed a
 322             // longer one.
 323             if((flags & match_not_null) && (first == temp_match[0].first))
 324                goto failure;
 325             temp_match.set_second(first);
 326             m.maybe_assign(temp_match);
 327             match_found = true;
 328             if(((flags & match_any) && ((first == last) || !(flags & match_all))) || ((first == last) && (need_push_match == false)))
 329             {
 330                // either we don't care what we match or we've matched
 331                // the whole string and can't match anything longer.
 332                while(matches.empty() == false)
 333                   matches.pop();
 334                while(prev_pos.empty() == false)
 335                   prev_pos.pop();
 336                while(prev_record.empty() == false)
 337                   prev_record.pop();
 338                while(prev_acc.empty() == false)
 339                   prev_acc.pop();
 340                return true;
 341             }
 342          }
 343          goto failure;
 344       case syntax_element_startmark:
 345          if(((re_brace*)ptr)->index > 0)
 346             temp_match.set_first(first, ((re_brace*)ptr)->index);
 347          ptr = ptr->next.p;
 348          break;
 349       case syntax_element_endmark:
 350          if(((re_brace*)ptr)->index > 0)
 351             temp_match.set_second(first, ((re_brace*)ptr)->index);
 352          ptr = ptr->next.p;
 353          break;
 354       case syntax_element_literal:
 355       {
 356          unsigned int len = ((re_literal*)ptr)->length;
 357          charT* what = (charT*)(((re_literal*)ptr) + 1);
 358          //
 359          // compare string with what we stored in
 360          // our records:
 361          for(unsigned int i = 0; i < len; ++i, ++first)
 362          {
 363             if((first == last) || (traits_inst.translate(*first, icase) != what[i]))
 364                goto failure;
 365          }
 366          ptr = ptr->next.p;
 367          break;
 368       }
 369       case syntax_element_start_line:
 370          outer_line_check:
 371          if(first == temp_match[0].first)
 372          {
 373             // we're at the start of the buffer
 374             if(flags & match_prev_avail)
 375             {
 376                inner_line_check:
 377                // check the previous value even though its before
 378                // the start of our "buffer".
 379                iterator t(first);
 380                --t;
 381                if(traits::is_separator(*t) && !((*t == '\r') && (*first == '\n')) )
 382                {
 383                   ptr = ptr->next.p;
 384                   continue;
 385                }
 386                goto failure;
 387             }
 388             if((flags & match_not_bol) == 0)
 389             {
 390                ptr = ptr->next.p;
 391                continue;
 392             }
 393             goto failure;
 394          }
 395          // we're in the middle of the string
 396          goto inner_line_check;
 397       case syntax_element_end_line:
 398          // we're not yet at the end so *first is always valid:
 399          if(traits::is_separator(*first))
 400          {
 401             if((first != base) || (flags & match_prev_avail))
 402             {
 403                // check that we're not in the middle of \r\n sequence
 404                iterator t(first);
 405                --t;
 406                if((*t == '\r') && (*first == '\n'))
 407                {
 408                   goto failure;
 409                }
 410             }
 411             ptr = ptr->next.p;
 412             continue;
 413          }
 414          goto failure;
 415       case syntax_element_wild:
 416          // anything except possibly NULL or \n:
 417          if(traits::is_separator(*first))
 418          {
 419             if(flags & match_not_dot_newline)
 420                goto failure;
 421             ptr = ptr->next.p;
 422             ++first;
 423             continue;
 424          }
 425          if(*first == charT(0))
 426          {
 427             if(flags & match_not_dot_null)
 428                goto failure;
 429             ptr = ptr->next.p;
 430             ++first;
 431             continue;
 432          }
 433          ptr = ptr->next.p;
 434          ++first;
 435          break;
 436       case syntax_element_word_boundary:
 437       {
 438          // prev and this character must be opposites:
 439          bool b = traits_inst.is_class(*first, traits::char_class_word);
 440          if((first == temp_match[0].first)  && ((flags & match_prev_avail) == 0))
 441          {
 442             if(flags & match_not_bow)
 443                b ^= true;
 444             else
 445                b ^= false;
 446          }
 447          else
 448          {
 449             --first;
 450             b ^= traits_inst.is_class(*first, traits::char_class_word);
 451             ++first;
 452          }
 453          if(b)
 454          {
 455             ptr = ptr->next.p;
 456             continue;
 457          }
 458          goto failure;
 459       }
 460       case syntax_element_within_word:
 461          // both prev and this character must be traits::char_class_word:
 462          if(traits_inst.is_class(*first, traits::char_class_word))
 463          {
 464             bool b;
 465             if((first == temp_match[0].first) && ((flags & match_prev_avail) == 0))
 466                b = false;
 467             else
 468             {
 469                --first;
 470                b = traits_inst.is_class(*first, traits::char_class_word);
 471                ++first;
 472             }
 473             if(b)
 474             {
 475                ptr = ptr->next.p;
 476                continue;
 477             }
 478          }
 479          goto failure;
 480       case syntax_element_word_start:
 481          if((first == temp_match[0].first) && ((flags & match_prev_avail) == 0))
 482          {
 483             // start of buffer:
 484             if(flags & match_not_bow)
 485                goto failure;
 486             if(traits_inst.is_class(*first, traits::char_class_word))
 487             {
 488                ptr = ptr->next.p;
 489                continue;
 490             }
 491             goto failure;
 492          }
 493          // otherwise inside buffer:
 494          if(traits_inst.is_class(*first, traits::char_class_word))
 495          {
 496             iterator t(first);
 497             --t;
 498             if(traits_inst.is_class(*t, traits::char_class_word) == false)
 499             {
 500                ptr = ptr->next.p;
 501                continue;
 502             }
 503          }
 504          goto failure;      // if we fall through to here then we've failed
 505       case syntax_element_word_end:
 506          if((first == temp_match[0].first) && ((flags & match_prev_avail) == 0))
 507             goto failure;  // start of buffer can't be end of word
 508
 509          // otherwise inside buffer:
 510          if(traits_inst.is_class(*first, traits::char_class_word) == false)
 511          {
 512             iterator t(first);
 513             --t;
 514             if(traits_inst.is_class(*t, traits::char_class_word))
 515             {
 516                ptr = ptr->next.p;
 517                continue;
 518             }
 519          }
 520          goto failure;      // if we fall through to here then we've failed
 521       case syntax_element_buffer_start:
 522          if((first != temp_match[0].first) || (flags & match_not_bob))
 523             goto failure;
 524          // OK match:
 525          ptr = ptr->next.p;
 526          break;
 527       case syntax_element_buffer_end:
 528          if((first != last) || (flags & match_not_eob))
 529             goto failure;
 530          // OK match:
 531          ptr = ptr->next.p;
 532          break;
 533       case syntax_element_backref:
 534       {
 535          // compare with what we previously matched:
 536          iterator i = temp_match[((re_brace*)ptr)->index].first;
 537          iterator j = temp_match[((re_brace*)ptr)->index].second;
 538          while(i != j)
 539          {
 540             if((first == last) || (traits_inst.translate(*first, icase) != traits_inst.translate(*i, icase)))
 541                goto failure;
 542             ++i;
 543             ++first;
 544          }
 545          ptr = ptr->next.p;
 546          break;
 547       }
 548       case syntax_element_long_set:
 549       {
 550          // let the traits class do the work:
 551          iterator t = re_is_set_member(first, last, (re_set_long*)ptr, e);
 552          if(t != first)
 553          {
 554             ptr = ptr->next.p;
 555             first = t;
 556             continue;
 557          }
 558          goto failure;
 559       }
 560       case syntax_element_set:
 561          // lookup character in table:
 562          if(((re_set*)ptr)->_map[(traits_uchar_type)traits_inst.translate(*first, icase)])
 563          {
 564             ptr = ptr->next.p;
 565             ++first;
 566             continue;
 567          }
 568          goto failure;
 569       case syntax_element_jump:
 570          ptr = ((re_jump*)ptr)->alt.p;
 571          continue;
 572       case syntax_element_alt:
 573       {
 574          // alt_jump:
 575          if(access::can_start(*first, ((re_jump*)ptr)->_map, (unsigned char)mask_take))
 576          {
 577             // we can take the first alternative,
 578             // see if we need to push next alternative:
 579             if(access::can_start(*first, ((re_jump*)ptr)->_map, mask_skip))
 580             {
 581                if(need_push_match)
 582                   matches.push(temp_match);
 583                for(k = 0; k <= cur_acc; ++k)
 584                   prev_pos.push(start_loop[k]);
 585                prev_pos.push(first);
 586                prev_record.push(ptr);
 587                for(k = 0; k <= cur_acc; ++k)
 588                   prev_acc.push(accumulators[k]);
 589                prev_acc.push(cur_acc);
 590             }
 591             ptr = ptr->next.p;
 592             continue;
 593          }
 594          if(access::can_start(*first, ((re_jump*)ptr)->_map, mask_skip))
 595          {
 596             ptr = ((re_jump*)ptr)->alt.p;
 597             continue;
 598          }
 599          goto failure;  // neither option is possible
 600       }
 601       case syntax_element_rep:
 602       {
 603          // repeater_jump:
 604          // if we're moving to a higher id (nested repeats etc)
 605          // zero out our accumualtors:
 606          if(cur_acc < ((re_repeat*)ptr)->id)
 607          {
 608             cur_acc = ((re_repeat*)ptr)->id;
 609             accumulators[cur_acc] = 0;
 610             start_loop[cur_acc] = first;
 611          }
 612
 613          cur_acc = ((re_repeat*)ptr)->id;
 614
 615          if(((re_repeat*)ptr)->leading)
 616             *restart = first;
 617
 618          //charT c = traits_inst.translate(*first);
 619
 620          // first of all test for special case where this is last element,
 621          // if that is the case then repeat as many times as possible,
 622          // as long as the repeat is greedy:
 623
 624          if((((re_repeat*)ptr)->alt.p->type == syntax_element_match)
 625             && (((re_repeat*)ptr)->greedy == true))
 626          {
 627             // see if we can take the repeat:
 628             if(((unsigned int)accumulators[cur_acc] < ((re_repeat*)ptr)->max)
 629                   && access::can_start(*first, ((re_repeat*)ptr)->_map, mask_take))
 630             {
 631                // push terminating match as fallback:
 632                if((unsigned int)accumulators[cur_acc] >= ((re_repeat*)ptr)->min)
 633                {
 634                   if((prev_record.empty() == false) && (prev_record.peek() == ((re_repeat*)ptr)->alt.p))
 635                   {
 636                      // we already have the required fallback
 637                      // don't add any more, just update this one:
 638                      if(need_push_match)
 639                         matches.peek() = temp_match;
 640                      prev_pos.peek() = first;
 641                   }
 642                   else
 643                   {
 644                      if(need_push_match)
 645                         matches.push(temp_match);
 646                      prev_pos.push(first);
 647                      prev_record.push(((re_repeat*)ptr)->alt.p);
 648                   }
 649                }
 650                // move to next item in list:
 651                if((first != start_loop[cur_acc]) || !accumulators[cur_acc])
 652                {
 653                   ++accumulators[cur_acc];
 654                   ptr = ptr->next.p;
 655                   start_loop[cur_acc] = first;
 656                   continue;
 657                }
 658                goto failure;
 659             }
 660             // see if we can skip the repeat:
 661             if(((unsigned int)accumulators[cur_acc] >= ((re_repeat*)ptr)->min)
 662                && access::can_start(*first, ((re_repeat*)ptr)->_map, mask_skip))
 663             {
 664                ptr = ((re_repeat*)ptr)->alt.p;
 665                continue;
 666             }
 667             // otherwise fail:
 668             goto failure;
 669          }
 670
 671          // OK if we get to here then the repeat is either non-terminal or non-greedy,
 672          // see if we can skip the repeat:
 673          if(((unsigned int)accumulators[cur_acc] >= ((re_repeat*)ptr)->min)
 674             && access::can_start(*first, ((re_repeat*)ptr)->_map, mask_skip))
 675          {
 676             // see if we can push failure info:
 677             if(((unsigned int)accumulators[cur_acc] < ((re_repeat*)ptr)->max)
 678                && access::can_start(*first, ((re_repeat*)ptr)->_map, mask_take))
 679             {
 680                // check to see if the last loop matched a NULL string
 681                // if so then we really don't want to loop again:
 682                if(((unsigned int)accumulators[cur_acc] == ((re_repeat*)ptr)->min)
 683                   || (first != start_loop[cur_acc]))
 684                {
 685                   if(need_push_match)
 686                      matches.push(temp_match);
 687                   prev_pos.push(first);
 688                   prev_record.push(ptr);
 689                   for(k = 0; k <= cur_acc; ++k)
 690                      prev_acc.push(accumulators[k]);
 691                   // for non-greedy repeats save whether we have a match already:
 692                   if(((re_repeat*)ptr)->greedy == false)
 693                   {
 694                      prev_acc.push(match_found);
 695                      match_found = false;
 696                   }
 697                }
 698             }
 699             ptr = ((re_repeat*)ptr)->alt.p;
 700             continue;
 701          }
 702
 703          // otherwise see if we can take the repeat:
 704          if(((unsigned int)accumulators[cur_acc] < ((re_repeat*)ptr)->max)
 705                && access::can_start(*first, ((re_repeat*)ptr)->_map, mask_take) &&
 706                ((first != start_loop[cur_acc]) || !accumulators[cur_acc]))
 707          {
 708             // move to next item in list:
 709             ++accumulators[cur_acc];
 710             ptr = ptr->next.p;
 711             start_loop[cur_acc] = first;
 712             continue;
 713          }
 714
 715          // if we get here then neither option is allowed so fail:
 716          goto failure;
 717
 718       }
 719       case syntax_element_combining:
 720          if(traits_inst.is_combining(traits_inst.translate(*first, icase)))
 721             goto failure;
 722          ++first;
 723          while((first != last) && traits_inst.is_combining(traits_inst.translate(*first, icase)))++first;
 724          ptr = ptr->next.p;
 725          continue;
 726       case syntax_element_soft_buffer_end:
 727          {
 728             if(flags & match_not_eob)
 729                goto failure;
 730             iterator p(first);
 731             while((p != last) && traits_inst.is_separator(traits_inst.translate(*first, icase)))++p;
 732             if(p != last)
 733                goto failure;
 734             ptr = ptr->next.p;
 735             continue;
 736          }
 737       case syntax_element_restart_continue:
 738          if(first != temp_match[-1].first)
 739             goto failure;
 740          ptr = ptr->next.p;
 741          continue;
 742       default:
 743          jm_assert(0); // should never get to here!!
 744          return false;
 745       }
 746    }
 747
 748    //
 749    // if we get to here then we've run out of characters to match against,
 750    // we could however still have non-character regex items left
 751    if((ptr->can_be_null == 0) && ((flags & match_partial) == 0))
 752       goto failure;
 753    while(true)
 754    {
 755       jm_assert(ptr);
 756       switch(ptr->type)
 757       {
 758       case syntax_element_match:
 759          goto match_jump;
 760       case syntax_element_startmark:
 761          temp_match.set_first(first, ((re_brace*)ptr)->index);
 762          ptr = ptr->next.p;
 763          break;
 764       case syntax_element_endmark:
 765          temp_match.set_second(first, ((re_brace*)ptr)->index);
 766          ptr = ptr->next.p;
 767          break;
 768       case syntax_element_start_line:
 769          goto outer_line_check;
 770       case syntax_element_end_line:
 771          // we're at the end so *first is never valid:
 772          if((flags & match_not_eol) == 0)
 773          {
 774             ptr = ptr->next.p;
 775             continue;
 776          }
 777          goto failure;
 778       case syntax_element_word_boundary:
 779       case syntax_element_word_end:
 780          if(((flags & match_not_eow) == 0) && (first != temp_match[0].first))
 781          {
 782             iterator t(first);
 783             --t;
 784             if(traits_inst.is_class(*t, traits::char_class_word))
 785             {
 786                ptr = ptr->next.p;
 787                continue;
 788             }
 789          }
 790          goto failure;
 791       case syntax_element_buffer_end:
 792       case syntax_element_soft_buffer_end:
 793          if(flags & match_not_eob)
 794             goto failure;
 795          // OK match:
 796          ptr = ptr->next.p;
 797          break;
 798       case syntax_element_jump:
 799          ptr = ((re_jump*)ptr)->alt.p;
 800          continue;
 801       case syntax_element_alt:
 802          if(ptr->can_be_null & mask_take)
 803          {
 804             // we can test the first alternative,
 805             // see if we need to push next alternative:
 806             if(ptr->can_be_null & mask_skip)
 807             {
 808                if(need_push_match)
 809                   matches.push(temp_match);
 810                for(k = 0; k <= cur_acc; ++k)
 811                   prev_pos.push(start_loop[k]);
 812                prev_pos.push(first);
 813                prev_record.push(ptr);
 814                for(k = 0; k <= cur_acc; ++k)
 815                   prev_acc.push(accumulators[k]);
 816                prev_acc.push(cur_acc);
 817             }
 818             ptr = ptr->next.p;
 819             continue;
 820          }
 821          if(ptr->can_be_null & mask_skip)
 822          {
 823             ptr = ((re_jump*)ptr)->alt.p;
 824             continue;
 825          }
 826          goto failure;  // neither option is possible
 827       case syntax_element_rep:
 828          // if we're moving to a higher id (nested repeats etc)
 829          // zero out our accumualtors:
 830          if(cur_acc < ((re_repeat*)ptr)->id)
 831          {
 832             cur_acc = ((re_repeat*)ptr)->id;
 833             accumulators[cur_acc] = 0;
 834             start_loop[cur_acc] = first;
 835          }
 836
 837          cur_acc = ((re_repeat*)ptr)->id;
 838
 839          // see if we can skip the repeat:
 840          if(((unsigned int)accumulators[cur_acc] >= ((re_repeat*)ptr)->min)
 841             && ((ptr->can_be_null & mask_skip) || (flags & match_partial)))
 842          {
 843             // don't push failure info, there's no point:
 844             ptr = ((re_repeat*)ptr)->alt.p;
 845             continue;
 846          }
 847
 848          // otherwise see if we can take the repeat:
 849          if(((unsigned int)accumulators[cur_acc] < ((re_repeat*)ptr)->max)
 850                && (((ptr->can_be_null & (mask_take | mask_skip)) == (mask_take | mask_skip))) || (flags & match_partial))
 851          {
 852             // move to next item in list:
 853             ++accumulators[cur_acc];
 854             ptr = ptr->next.p;
 855             start_loop[cur_acc] = first;
 856             continue;
 857          }
 858
 859          // if we get here then neither option is allowed so fail:
 860          goto failure;
 861       case syntax_element_restart_continue:
 862          if(first != temp_match[-1].first)
 863             goto failure;
 864          ptr = ptr->next.p;
 865          continue;
 866       default:
 867          goto failure;
 868       }
 869    }
 870
 871    failure:
 872
 873    //
 874    // check for possible partial match:
 875    //
 876    if((flags & match_partial)
 877       && !match_found          // no full match already
 878       && (base != first)       // some charcters have been consumed
 879       && (first == last))      // end of input has been reached
 880    {
 881       have_partial_match = true;
 882       m.maybe_assign(temp_match);
 883    }
 884
 885    if(prev_record.empty() == false)
 886    {
 887       ptr = prev_record.peek();
 888       switch(ptr->type)
 889       {
 890       case syntax_element_alt:
 891          // get next alternative:
 892          ptr = ((re_jump*)ptr)->alt.p;
 893          if(need_push_match)
 894             matches.pop(temp_match);
 895          prev_acc.pop(cur_acc);
 896          for(k = cur_acc; k >= 0; --k)
 897             prev_acc.pop(accumulators[k]);
 898          prev_pos.pop(first);
 899          for(k = cur_acc; k >= 0; --k)
 900             prev_pos.pop(start_loop[k]);
 901          prev_record.pop();
 902          goto retry;
 903       case syntax_element_rep:
 904       {
 905          // we're doing least number of repeats first,
 906          // increment count and repeat again:
 907          bool saved_matched = match_found;
 908          if(need_push_match)
 909             matches.pop(temp_match);
 910          prev_pos.pop(first);
 911          cur_acc = ((re_repeat*)ptr)->id;
 912          if(((re_repeat*)ptr)->greedy == false)
 913          {
 914             saved_matched = prev_acc.peek();
 915             prev_acc.pop();
 916          }
 917          for(k = cur_acc; k >= 0; --k)
 918             prev_acc.pop(accumulators[k]);
 919          prev_record.pop();
 920          if((unsigned int)++accumulators[cur_acc] > ((re_repeat*)ptr)->max)
 921             goto failure;  // repetions exhausted.
 922          //
 923          // if the repeat is non-greedy, and we found a match then fail again:
 924          if((((re_repeat*)ptr)->greedy == false) && (match_found == true))
 925          {
 926             goto failure;
 927          }
 928          else if (match_found == false)
 929             match_found = saved_matched;
 930          ptr = ptr->next.p;
 931          start_loop[cur_acc] = first;
 932          goto retry;
 933       }
 934       case syntax_element_match:
 935          if(need_push_match)
 936             matches.pop(temp_match);
 937          prev_pos.pop(first);
 938          prev_record.pop();
 939          goto retry;
 940      default:
 941          jm_assert(0);
 942          // mustn't get here!!
 943       }
 944    }
 945
 946    if(match_found || have_partial_match)
 947       return true;
 948
 949    // if we get to here then everything has failed
 950    // and no match was found:
 951    return false;
 952 }
 953 #if defined(BOOST_RE_NO_TEMPLATE_SWITCH_MERGE) && !defined(BOOST_RE_NO_NAMESPACES)
 954 } // namespace
 955 #endif
 956
 957
 958 template <class iterator>
 959 void _skip_and_inc(unsigned int& clines, iterator& last_line, iterator& first, const iterator last)
 960 {
 961    while(first != last)
 962    {
 963       if(*first == '\n')
 964       {
 965          last_line = ++first;
 966          ++clines;
 967       }
 968       else
 969          ++first;
 970    }
 971 }
 972
 973 template <class iterator>
 974 void _skip_and_dec(unsigned int& clines, iterator& last_line, iterator& first, iterator base, unsigned int len)
 975 {
 976    bool need_line = false;
 977    for(unsigned int i = 0; i < len; ++i)
 978    {
 979       --first;
 980       if(*first == '\n')
 981       {
 982          need_line = true;
 983          --clines;
 984       }
 985    }
 986
 987    if(need_line)
 988    {
 989       last_line = first;
 990
 991       if(last_line != base)
 992          --last_line;
 993       else
 994          return;
 995
 996       while((last_line != base) && (*last_line != '\n'))
 997          --last_line;
 998       if(*last_line == '\n')
 999          ++last_line;
1000    }
1001 }
1002
1003 template <class iterator>
1004 inline void _inc_one(unsigned int& clines, iterator& last_line, iterator& first)
1005 {
1006    if(*first == '\n')
1007    {
1008       last_line = ++first;
1009       ++clines;
1010    }
1011    else
1012       ++first;
1013 }
1014
1015 template <class iterator, class Allocator>
1016 struct grep_search_predicate
1017 {
1018    match_results<iterator, Allocator>* pm;
1019    grep_search_predicate(match_results<iterator, Allocator>* p) : pm(p) {}
1020    bool operator()(const match_results<iterator, Allocator>& m)
1021    {
1022       *pm = static_cast<const match_results_base<iterator, Allocator>&>(m);
1023       return false;
1024    }
1025 };
1026
1027 #if !defined(BOOST_RE_NO_TEMPLATE_RETURNS) && !defined(BOOST_RE_NO_PARTIAL_FUNC_SPEC)
1028
1029 template <class iterator, class Allocator>
1030 inline const match_results_base<iterator, Allocator>& grep_out_type(const grep_search_predicate<iterator, Allocator>& o, const Allocator&)
1031 {
1032    return *(o.pm);
1033 }
1034
1035 #endif
1036
1037 template <class T, class Allocator>
1038 inline const Allocator& grep_out_type(const T&, const Allocator& a)
1039 {
1040    return a;
1041 }
1042
1043 #if defined(BOOST_RE_NO_TEMPLATE_SWITCH_MERGE) && !defined(BOOST_RE_NO_NAMESPACES)
1044 //
1045 // Ugly ugly hack,
1046 // template don't merge if they contain switch statements so declare these
1047 // templates in unnamed namespace (ie with internal linkage), each translation
1048 // unit then gets its own local copy, it works seemlessly but bloats the app.
1049 namespace{
1050 #endif
1051
1052 //
1053 // reg_grep2:
1054 // find all non-overlapping matches within the sequence first last:
1055 //
1056 template <class Predicate, class I, class charT, class traits, class A, class A2>
1057 unsigned int reg_grep2(Predicate foo, I first, I last, const reg_expression<charT, traits, A>& e, unsigned flags, A2 a)
1058 {
1059    typedef access_t<charT, traits, A> access;
1060
1061    if(e.flags() & regbase::failbit)
1062       return 0;
1063
1064    typedef typename traits::size_type traits_size_type;
1065    typedef typename traits::uchar_type traits_uchar_type;
1066    typedef typename is_byte<charT>::width_type width_type;
1067
1068    match_results<I, A2> m(grep_out_type(foo, a));
1069    I restart;
1070    m.set_size(e.mark_count(), first, last);
1071    m.set_line(1, first);
1072    m.set_base(first);
1073
1074    unsigned int clines = 1;
1075    unsigned int cmatches = 0;
1076    I last_line = first;
1077    I next_base;
1078    I base = first;
1079    bool need_init;
1080    const traits& traits_inst = e.get_traits();
1081    // dwa 9/13/00 suppress incorrect MSVC warning - it claims this is never
1082    // referenced
1083    (void)traits_inst;
1084
1085    flags |= match_init;
1086
1087    _priv_match_data<I, A2> pd(m);
1088
1089    const unsigned char* _map = access::get_map(e);
1090    unsigned int type;
1091
1092    if(first == last)
1093    {
1094       // special case, only test if can_be_null,
1095       // don't dereference any pointers!!
1096       if(access::first(e)->can_be_null)
1097       {
1098          if(query_match_aux(first, last, m, e, flags, pd, &restart))
1099          {
1100             foo(m);
1101             ++cmatches;
1102          }
1103       }
1104       return cmatches;
1105    }
1106
1107    // try one time whatever:
1108    if( access::can_start(*first, _map, (unsigned char)mask_any) )
1109    {
1110       if(query_match_aux(first, last, m, e, flags, pd, &restart))
1111       {
1112          ++cmatches;
1113          if(foo(m) == false)
1114             return cmatches;
1115          // update to end of what matched
1116          // trying to match again with match_not_null set if this
1117          // is a null match...
1118          need_init = true;
1119          if(first == m[0].second)
1120          {
1121             next_base = m[0].second;
1122             pd.temp_match.init_fail(next_base, last);
1123             m.init_fail(next_base, last);
1124             if(query_match_aux(first, last, m, e, flags | match_not_null, pd, &restart))
1125             {
1126                ++cmatches;
1127                if(foo(m) == false)
1128                   return cmatches;
1129             }
1130             else
1131             {
1132                need_init = false;
1133                for(unsigned int i = 0; (restart != first) && (i < access::leading_length(e)); ++i, --restart)
1134                    {} // dwa 10/20/2000 - warning suppression for MWCW
1135                if(restart != last)
1136                   ++restart;
1137                _skip_and_inc(clines, last_line, first, restart);
1138             }
1139          }
1140          if(need_init)
1141          {
1142             _skip_and_inc(clines, last_line, first, m[0].second);
1143             next_base = m[0].second;
1144             pd.temp_match.init_fail(next_base, last);
1145             m.init_fail(next_base, last);
1146          }
1147       }
1148       else
1149       {
1150          for(unsigned int i = 0; (restart != first) && (i < access::leading_length(e)); ++i, --restart)
1151              {} // dwa 10/20/2000 - warning suppression for MWCW
1152          if(restart != last)
1153             ++restart;
1154          _skip_and_inc(clines, last_line, first, restart);
1155       }
1156    }
1157    else
1158       _inc_one(clines, last_line, first);
1159    flags |= match_prev_avail | match_not_bob;
1160
1161
1162    // depending on what the first record is we may be able to
1163    // optimise the search:
1164    type = (flags & match_continuous) ? regbase::restart_continue : access::restart_type(e);
1165
1166    if(type == regbase::restart_buf)
1167       return cmatches;
1168
1169    switch(type)
1170    {
1171    case regbase::restart_lit:
1172    case regbase::restart_fixed_lit:
1173    {
1174       const kmp_info<charT>* info = access::get_kmp(e);
1175       int len = info->len;
1176       const charT* x = info->pstr;
1177       int j = 0;
1178       bool icase = e.flags() & regbase::icase;
1179       while (first != last)
1180       {
1181          while((j > -1) && (x[j] != traits_inst.translate(*first, icase)))
1182             j = info->kmp_next[j];
1183          _inc_one(clines, last_line, first);
1184          ++j;
1185          if(j >= len)
1186          {
1187             if(type == regbase::restart_fixed_lit)
1188             {
1189                _skip_and_dec(clines, last_line, first, base, j);
1190                restart = first;
1191                restart += len;
1192                m.set_first(first);
1193                m.set_second(restart);
1194                m.set_line(clines, last_line);
1195                ++cmatches;
1196                if(foo(m) == false)
1197                   return cmatches;
1198                _skip_and_inc(clines, last_line, first, restart);
1199                next_base = m[0].second;
1200                pd.temp_match.init_fail(next_base, last);
1201                m.init_fail(next_base, last);
1202                j = 0;
1203             }
1204             else
1205             {
1206                restart = first;
1207                _skip_and_dec(clines, last_line, first, base, j);
1208                if(query_match_aux(first, last, m, e, flags, pd, &restart))
1209                {
1210
1211                   m.set_line(clines, last_line);
1212                   ++cmatches;
1213                   if(foo(m) == false)
1214                      return cmatches;
1215                   // update to end of what matched
1216                  _skip_and_inc(clines, last_line, first, m[0].second);
1217                   next_base = m[0].second;
1218                   pd.temp_match.init_fail(next_base, last);
1219                   m.init_fail(next_base, last);
1220                   j = 0;
1221                }
1222                else
1223                {
1224                   for(int k = 0; (restart != first) && (k < j); ++k, --restart)
1225                       {} // dwa 10/20/2000 - warning suppression for MWCW
1226                   if(restart != last)
1227                      ++restart;
1228                   _skip_and_inc(clines, last_line, first, restart);
1229                   j = 0;  //we could do better than this...
1230                }
1231             }
1232          }
1233       }
1234       break;
1235    }
1236    case regbase::restart_any:
1237    {
1238       while(first != last)
1239       {
1240          if( access::can_start(*first, _map, (unsigned char)mask_any) )
1241          {
1242             if(query_match_aux(first, last, m, e, flags, pd, &restart))
1243             {
1244
1245                m.set_line(clines, last_line);
1246                ++cmatches;
1247                if(foo(m) == false)
1248                   return cmatches;
1249                // update to end of what matched
1250                // trying to match again with match_not_null set if this
1251                // is a null match...
1252                need_init = true;
1253                if(first == m[0].second)
1254                {
1255                   next_base = m[0].second;
1256                   pd.temp_match.init_fail(next_base, last);
1257                   m.init_fail(next_base, last);
1258                   if(query_match_aux(first, last, m, e, flags | match_not_null, pd, &restart))
1259                   {
1260                      m.set_line(clines, last_line);
1261                      ++cmatches;
1262                      if(foo(m) == false)
1263                         return cmatches;
1264                   }
1265                   else
1266                   {
1267                      need_init = false;
1268                      for(unsigned int i = 0; (restart != first) && (i < access::leading_length(e)); ++i, --restart)
1269                          {} // dwa 10/20/2000 - warning suppression for MWCW
1270                      if(restart != last)
1271                         ++restart;
1272                      _skip_and_inc(clines, last_line, first, restart);
1273                   }
1274                }
1275                if(need_init)
1276                {
1277                  _skip_and_inc(clines, last_line, first, m[0].second);
1278                   next_base = m[0].second;
1279                   pd.temp_match.init_fail(next_base, last);
1280                   m.init_fail(next_base, last);
1281                }
1282                continue;
1283             }
1284             else
1285             {
1286                for(unsigned int i = 0; (restart != first) && (i < access::leading_length(e)); ++i, --restart)
1287                    {} // dwa 10/20/2000 - warning suppression for MWCW
1288                if(restart != last)
1289                   ++restart;
1290                _skip_and_inc(clines, last_line, first, restart);
1291             }
1292          }
1293          else
1294             _inc_one(clines, last_line, first);
1295       }
1296    }
1297    break;
1298    case regbase::restart_word:
1299    {
1300       // do search optimised for word starts:
1301       while(first != last)
1302       {
1303          --first;
1304          if(*first == '\n')
1305             --clines;
1306          // skip the word characters:
1307          while((first != last) && traits_inst.is_class(*first, traits::char_class_word))
1308             ++first;
1309          // now skip the white space:
1310          while((first != last) && (traits_inst.is_class(*first, traits::char_class_word) == false))
1311          {
1312          #ifdef __GNUC__
1313             //
1314             // hack to work around gcc optimisation bug
1315             // just expand the contents of _inc_one here:
1316             if(*first == '\n')
1317             {
1318                last_line = ++first;
1319                ++clines;
1320             }
1321             else
1322                ++first;
1323          #else
1324             _inc_one(clines, last_line, first);
1325          #endif
1326          }
1327          if(first == last)
1328             break;
1329
1330          if( access::can_start(*first, _map, (unsigned char)mask_any) )
1331          {
1332             if(query_match_aux(first, last, m, e, flags, pd, &restart))
1333             {
1334                m.set_line(clines, last_line);
1335                ++cmatches;
1336                if(foo(m) == false)
1337                   return cmatches;
1338                // update to end of what matched
1339                // trying to match again with match_not_null set if this
1340                // is a null match...
1341                need_init = true;
1342                if(first == m[0].second)
1343                {
1344                   next_base = m[0].second;
1345                   pd.temp_match.init_fail(next_base, last);
1346                   m.init_fail(next_base, last);
1347                   if(query_match_aux(first, last, m, e, flags | match_not_null, pd, &restart))
1348                   {
1349                      m.set_line(clines, last_line);
1350                      ++cmatches;
1351                      if(foo(m) == false)
1352                         return cmatches;
1353                   }
1354                   else
1355                   {
1356                      need_init = false;
1357                      for(unsigned int i = 0; (restart != first) && (i < access::leading_length(e)); ++i, --restart)
1358                          {} // dwa 10/20/2000 - warning suppression for MWCW
1359                      if(restart != last)
1360                         ++restart;
1361                      _skip_and_inc(clines, last_line, first, restart);
1362                   }
1363                }
1364                if(need_init)
1365                {
1366                   _skip_and_inc(clines, last_line, first, m[0].second);
1367                   next_base = m[0].second;
1368                   pd.temp_match.init_fail(next_base, last);
1369                   m.init_fail(next_base, last);
1370                }
1371             }
1372             else
1373             {
1374                for(unsigned int i = 0; (restart != first) && (i < access::leading_length(e)); ++i, --restart)
1375                    {} // dwa 10/20/2000 - warning suppression for MWCW
1376                if(restart != last)
1377                   ++restart;
1378                _skip_and_inc(clines, last_line, first, restart);
1379             }
1380          }
1381          else
1382             _inc_one(clines, last_line, first);
1383       }
1384    }
1385    break;
1386    case regbase::restart_line:
1387    {
1388       // do search optimised for line starts:
1389       while(first != last)
1390       {
1391          // find first charcter after a line break:
1392          --first;
1393          if(*first == '\n')
1394             --clines;
1395          while((first != last) && (*first != '\n'))
1396             ++first;
1397          if(first == last)
1398             break;
1399          ++first;
1400          if(first == last)
1401             break;
1402
1403          ++clines;
1404          last_line = first;
1405
1406          if( access::can_start(*first, _map, (unsigned char)mask_any) )
1407          {
1408             if(query_match_aux(first, last, m, e, flags, pd, &restart))
1409             {
1410                m.set_line(clines, last_line);
1411                ++cmatches;
1412                if(foo(m) == false)
1413                   return cmatches;
1414                // update to end of what matched
1415                // trying to match again with match_not_null set if this
1416                // is a null match...
1417                need_init = true;
1418                if(first == m[0].second)
1419                {
1420                   next_base = m[0].second;
1421                   pd.temp_match.init_fail(next_base, last);
1422                   m.init_fail(next_base, last);
1423                   if(query_match_aux(first, last, m, e, flags | match_not_null, pd, &restart))
1424                   {
1425                      m.set_line(clines, last_line);
1426                      ++cmatches;
1427                      if(foo(m) == false)
1428                         return cmatches;
1429                   }
1430                   else
1431                   {
1432                      need_init = false;
1433                      for(unsigned int i = 0; (restart != first) && (i < access::leading_length(e)); ++i, --restart)
1434                          {} // dwa 10/20/2000 - warning suppression for MWCW
1435                      if(restart != last)
1436                         ++restart;
1437                      _skip_and_inc(clines, last_line, first, restart);
1438                   }
1439                }
1440                if(need_init)
1441                {
1442                   _skip_and_inc(clines, last_line, first, m[0].second);
1443                   next_base = m[0].second;
1444                   pd.temp_match.init_fail(next_base, last);
1445                   m.init_fail(next_base, last);
1446                }
1447             }
1448             else
1449             {
1450                for(unsigned int i = 0; (restart != first) && (i < access::leading_length(e)); ++i, --restart)
1451                    {} // dwa 10/20/2000 - warning suppression for MWCW
1452                if(restart != last)
1453                   ++restart;
1454                _skip_and_inc(clines, last_line, first, restart);
1455             }
1456          }
1457          else
1458             _inc_one(clines, last_line, first);
1459       }
1460    }
1461    break;
1462    case regbase::restart_continue:
1463    {
1464       while(first != last)
1465       {
1466          if( access::can_start(*first, _map, (unsigned char)mask_any) )
1467          {
1468             if(query_match_aux(first, last, m, e, flags, pd, &restart))
1469             {
1470                m.set_line(clines, last_line);
1471                ++cmatches;
1472                if(foo(m) == false)
1473                   return cmatches;
1474                // update to end of what matched
1475                // trying to match again with match_not_null set if this
1476                // is a null match...
1477                if(first == m[0].second)
1478                {
1479                   next_base = m[0].second;
1480                   pd.temp_match.init_fail(next_base, last);
1481                   m.init_fail(next_base, last);
1482                   if(query_match_aux(first, last, m, e, flags | match_not_null, pd, &restart))
1483                   {
1484                      m.set_line(clines, last_line);
1485                      ++cmatches;
1486                      if(foo(m) == false)
1487                         return cmatches;
1488                   }
1489                   else
1490                      return cmatches;  // can't continue from null match
1491                }
1492                _skip_and_inc(clines, last_line, first, m[0].second);
1493                next_base = m[0].second;
1494                pd.temp_match.init_fail(next_base, last);
1495                m.init_fail(next_base, last);
1496                continue;
1497             }
1498          }
1499          return cmatches;
1500       }
1501    }
1502    break;
1503    }
1504
1505
1506    // finally check trailing null string:
1507    if(access::first(e)->can_be_null)
1508    {
1509       if(query_match_aux(first, last, m, e, flags, pd, &restart))
1510       {
1511          m.set_line(clines, last_line);
1512          ++cmatches;
1513          if(foo(m) == false)
1514             return cmatches;
1515       }
1516    }
1517
1518    return cmatches;
1519 }
1520 #if defined(BOOST_RE_NO_TEMPLATE_SWITCH_MERGE) && !defined(BOOST_RE_NO_NAMESPACES)
1521 } // namespace {anon}
1522 #endif
1523
1524 } // namespace re_detail
1525
1526 //
1527 // proc regex_match
1528 // returns true if the specified regular expression matches
1529 // the whole of the input.  Fills in what matched in m.
1530 //
1531 template <class iterator, class Allocator, class charT, class traits, class Allocator2>
1532 bool regex_match(iterator first, iterator last, match_results<iterator, Allocator>& m, const reg_expression<charT, traits, Allocator2>& e, unsigned flags = match_default)
1533 {
1534    // prepare m for failure:
1535    if((flags & match_init) == 0)
1536    {
1537       m.set_size(e.mark_count(), first, last);
1538       m.set_base(first);
1539       m.set_line(1, first);
1540    }
1541    flags |= match_all; // must match all of input.
1542    re_detail::_priv_match_data<iterator, Allocator> pd(m);
1543    iterator restart;
1544    bool result = re_detail::query_match_aux(first, last, m, e, flags, pd, &restart);
1545    if(result && (last == m[0].second))
1546       return true;
1547    return false;
1548 }
1549 template <class iterator, class charT, class traits, class Allocator2>
1550 bool regex_match(iterator first, iterator last, const reg_expression<charT, traits, Allocator2>& e, unsigned flags = match_default)
1551 {
1552    match_results<iterator> m;
1553    return regex_match(first, last, m, e, flags);
1554 }
1555 //
1556 // query_match convenience interfaces:
1557 #ifndef BOOST_RE_NO_PARTIAL_FUNC_SPEC
1558 //
1559 // this isn't really a partial specialisation, but template function
1560 // overloading - if the compiler doesn't support partial specialisation
1561 // then it really won't support this either:
1562 template <class charT, class Allocator, class traits, class Allocator2>
1563 inline bool regex_match(const charT* str,
1564                         match_results<const charT*, Allocator>& m,
1565                         const reg_expression<charT, traits, Allocator2>& e,
1566                         unsigned flags = match_default)
1567 {
1568    return regex_match(str, str + traits::length(str), m, e, flags);
1569 }
1570
1571 template <class ST, class SA, class Allocator, class charT, class traits, class Allocator2>
1572 inline bool regex_match(const std::basic_string<charT, ST, SA>& s,
1573                  match_results<typename std::basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
1574                  const reg_expression<charT, traits, Allocator2>& e,
1575                  unsigned flags = match_default)
1576 {
1577    return regex_match(s.begin(), s.end(), m, e, flags);
1578 }
1579 template <class charT, class traits, class Allocator2>
1580 inline bool regex_match(const charT* str,
1581                         const reg_expression<charT, traits, Allocator2>& e,
1582                         unsigned flags = match_default)
1583 {
1584    match_results<const charT*> m;
1585    return regex_match(str, str + traits::length(str), m, e, flags);
1586 }
1587
1588 template <class ST, class SA, class charT, class traits, class Allocator2>
1589 inline bool regex_match(const std::basic_string<charT, ST, SA>& s,
1590                  const reg_expression<charT, traits, Allocator2>& e,
1591                  unsigned flags = match_default)
1592 {
1593    typedef typename std::basic_string<charT, ST, SA>::const_iterator iterator;
1594    match_results<iterator> m;
1595    return regex_match(s.begin(), s.end(), m, e, flags);
1596 }
1597 #else  // partial ordering
1598 inline bool regex_match(const char* str,
1599                         cmatch& m,
1600                         const regex& e,
1601                         unsigned flags = match_default)
1602 {
1603    return regex_match(str, str + regex::traits_type::length(str), m, e, flags);
1604 }
1605 inline bool regex_match(const char* str,
1606                         const regex& e,
1607                         unsigned flags = match_default)
1608 {
1609    match_results<const char*> m;
1610    return regex_match(str, str + regex::traits_type::length(str), m, e, flags);
1611 }
1612 #ifndef BOOST_RE_NO_WCSTRING
1613 inline bool regex_match(const wchar_t* str,
1614                         wcmatch& m,
1615                         const wregex& e,
1616                         unsigned flags = match_default)
1617 {
1618    return regex_match(str, str + wregex::traits_type::length(str), m, e, flags);
1619 }
1620 inline bool regex_match(const wchar_t* str,
1621                         const wregex& e,
1622                         unsigned flags = match_default)
1623 {
1624    match_results<const wchar_t*> m;
1625    return regex_match(str, str + wregex::traits_type::length(str), m, e, flags);
1626 }
1627 #endif
1628 inline bool regex_match(const std::string& s,
1629                         match_results<std::string::const_iterator, regex::allocator_type>& m,
1630                         const regex& e,
1631                         unsigned flags = match_default)
1632 {
1633    return regex_match(s.begin(), s.end(), m, e, flags);
1634 }
1635 inline bool regex_match(const std::string& s,
1636                         const regex& e,
1637                         unsigned flags = match_default)
1638 {
1639    match_results<std::string::const_iterator, regex::allocator_type> m;
1640    return regex_match(s.begin(), s.end(), m, e, flags);
1641 }
1642 #if !defined(BOOST_RE_NO_WCSTRING)
1643 inline bool regex_match(const std::basic_string<wchar_t>& s,
1644                         match_results<std::basic_string<wchar_t>::const_iterator, wregex::allocator_type>& m,
1645                         const wregex& e,
1646                         unsigned flags = match_default)
1647 {
1648    return regex_match(s.begin(), s.end(), m, e, flags);
1649 }
1650 inline bool regex_match(const std::basic_string<wchar_t>& s,
1651                         const wregex& e,
1652                         unsigned flags = match_default)
1653 {
1654    match_results<std::basic_string<wchar_t>::const_iterator, wregex::allocator_type> m;
1655    return regex_match(s.begin(), s.end(), m, e, flags);
1656 }
1657 #endif
1658
1659 #endif
1660
1661 template <class iterator, class Allocator, class charT, class traits, class Allocator2>
1662 bool regex_search(iterator first, iterator last, match_results<iterator, Allocator>& m, const reg_expression<charT, traits, Allocator2>& e, unsigned flags = match_default)
1663 {
1664    if(e.flags() & regbase::failbit)
1665       return false;
1666
1667    typedef typename traits::size_type traits_size_type;
1668    typedef typename traits::uchar_type traits_uchar_type;
1669
1670    return re_detail::reg_grep2(re_detail::grep_search_predicate<iterator, Allocator>(&m), first, last, e, flags, m.allocator());
1671 }
1672
1673 //
1674 // regex_search convenience interfaces:
1675 #ifndef BOOST_RE_NO_PARTIAL_FUNC_SPEC
1676 //
1677 // this isn't really a partial specialisation, but template function
1678 // overloading - if the compiler doesn't support partial specialisation
1679 // then it really won't support this either:
1680 template <class charT, class Allocator, class traits, class Allocator2>
1681 inline bool regex_search(const charT* str,
1682                         match_results<const charT*, Allocator>& m,
1683                         const reg_expression<charT, traits, Allocator2>& e,
1684                         unsigned flags = match_default)
1685 {
1686    return regex_search(str, str + traits::length(str), m, e, flags);
1687 }
1688
1689 template <class ST, class SA, class Allocator, class charT, class traits, class Allocator2>
1690 inline bool regex_search(const std::basic_string<charT, ST, SA>& s,
1691                  match_results<typename std::basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
1692                  const reg_expression<charT, traits, Allocator2>& e,
1693                  unsigned flags = match_default)
1694 {
1695    return regex_search(s.begin(), s.end(), m, e, flags);
1696 }
1697 #else  // partial specialisation
1698 inline bool regex_search(const char* str,
1699                         cmatch& m,
1700                         const regex& e,
1701                         unsigned flags = match_default)
1702 {
1703    return regex_search(str, str + regex::traits_type::length(str), m, e, flags);
1704 }
1705 #ifndef BOOST_RE_NO_WCSTRING
1706 inline bool regex_search(const wchar_t* str,
1707                         wcmatch& m,
1708                         const wregex& e,
1709                         unsigned flags = match_default)
1710 {
1711    return regex_search(str, str + wregex::traits_type::length(str), m, e, flags);
1712 }
1713 #endif
1714 inline bool regex_search(const std::string& s,
1715                         match_results<std::string::const_iterator, regex::allocator_type>& m,
1716                         const regex& e,
1717                         unsigned flags = match_default)
1718 {
1719    return regex_search(s.begin(), s.end(), m, e, flags);
1720 }
1721 #if !defined(BOOST_RE_NO_WCSTRING)
1722 inline bool regex_search(const std::basic_string<wchar_t>& s,
1723                         match_results<std::basic_string<wchar_t>::const_iterator, wregex::allocator_type>& m,
1724                         const wregex& e,
1725                         unsigned flags = match_default)
1726 {
1727    return regex_search(s.begin(), s.end(), m, e, flags);
1728 }
1729 #endif
1730
1731 #endif
1732
1733
1734 //
1735 // regex_grep:
1736 // find all non-overlapping matches within the sequence first last:
1737 //
1738 template <class Predicate, class iterator, class charT, class traits, class Allocator>
1739 inline unsigned int regex_grep(Predicate foo, iterator first, iterator last, const reg_expression<charT, traits, Allocator>& e, unsigned flags = match_default)
1740 {
1741    return re_detail::reg_grep2(foo, first, last, e, flags, e.allocator());
1742 }
1743
1744 //
1745 // regex_grep convenience interfaces:
1746 #ifndef BOOST_RE_NO_PARTIAL_FUNC_SPEC
1747 //
1748 // this isn't really a partial specialisation, but template function
1749 // overloading - if the compiler doesn't support partial specialisation
1750 // then it really won't support this either:
1751 template <class Predicate, class charT, class Allocator, class traits>
1752 inline unsigned int regex_grep(Predicate foo, const charT* str,
1753                         const reg_expression<charT, traits, Allocator>& e,
1754                         unsigned flags = match_default)
1755 {
1756    return regex_grep(foo, str, str + traits::length(str), e, flags);
1757 }
1758
1759 template <class Predicate, class ST, class SA, class Allocator, class charT, class traits>
1760 inline unsigned int regex_grep(Predicate foo, const std::basic_string<charT, ST, SA>& s,
1761                  const reg_expression<charT, traits, Allocator>& e,
1762                  unsigned flags = match_default)
1763 {
1764    return regex_grep(foo, s.begin(), s.end(), e, flags);
1765 }
1766 #else  // partial specialisation
1767 inline unsigned int regex_grep(bool (*foo)(const cmatch&), const char* str,
1768                         const regex& e,
1769                         unsigned flags = match_default)
1770 {
1771    return regex_grep(foo, str, str + regex::traits_type::length(str), e, flags);
1772 }
1773 #ifndef BOOST_RE_NO_WCSTRING
1774 inline unsigned int regex_grep(bool (*foo)(const wcmatch&), const wchar_t* str,
1775                         const wregex& e,
1776                         unsigned flags = match_default)
1777 {
1778    return regex_grep(foo, str, str + wregex::traits_type::length(str), e, flags);
1779 }
1780 #endif
1781 inline unsigned int regex_grep(bool (*foo)(const match_results<std::string::const_iterator, regex::allocator_type>&), const std::string& s,
1782                         const regex& e,
1783                         unsigned flags = match_default)
1784 {
1785    return regex_grep(foo, s.begin(), s.end(), e, flags);
1786 }
1787 #if !defined(BOOST_RE_NO_WCSTRING)
1788 inline unsigned int regex_grep(bool (*foo)(const match_results<std::basic_string<wchar_t>::const_iterator, wregex::allocator_type>&),
1789                      const std::basic_string<wchar_t>& s,
1790                         const wregex& e,
1791                         unsigned flags = match_default)
1792 {
1793    return regex_grep(foo, s.begin(), s.end(), e, flags);
1794 }
1795 #endif
1796
1797 #endif
1798
1799
1800 #ifdef __BORLANDC__
1801  #if __BORLANDC__ > 0x520
1802   #pragma option pop
1803  #endif
1804 #endif
1805
1806 } // namespace boost
1807
1808 #endif   // BOOST_REGEX_MATCH_HPP
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819