regex_match.hpp

boost库提供标准的C++ API 配合dev c++使用,功能更加强大

               }
               else if((unsigned int)accumulators[cur_acc] < static_cast<const re_repeat*>(ptr)->min)
               {
                  // the repeat was null, and we haven't gone round min times yet,
                  // since all subsequent repeats will be null as well, just update
                  // our repeat count and skip out.
                  accumulators[cur_acc] = static_cast<const re_repeat*>(ptr)->min;
                  ptr = static_cast<const re_repeat*>(ptr)->alt.p;
                  continue;
               }
               goto failure;
            }
            // see if we can skip the repeat:
            if(((unsigned int)accumulators[cur_acc] >= static_cast<const re_repeat*>(ptr)->min)
               && access::can_start(*first, static_cast<const re_repeat*>(ptr)->_map, mask_skip))
            {
               ptr = static_cast<const re_repeat*>(ptr)->alt.p;
               continue;
            }
            // otherwise fail:
            goto failure;
         }

         // OK if we get to here then the repeat is either non-terminal or non-greedy,
         // see if we can skip the repeat:
         if(((unsigned int)accumulators[cur_acc] >= static_cast<const re_repeat*>(ptr)->min)
            && access::can_start(*first, static_cast<const re_repeat*>(ptr)->_map, mask_skip))
         {
            // see if we can push failure info:
            if(((unsigned int)accumulators[cur_acc] < static_cast<const re_repeat*>(ptr)->max)
               && access::can_start(*first, static_cast<const re_repeat*>(ptr)->_map, mask_take))
            {
               // check to see if the last loop matched a NULL string
               // if so then we really don't want to loop again:
               if(((unsigned int)accumulators[cur_acc] == static_cast<const re_repeat*>(ptr)->min)
                  || (first != start_loop[cur_acc]))
               {
                  if(need_push_match)
                     matches.push(temp_match);
                  prev_pos.push(first);
                  prev_record.push(ptr);
                  for(k = 0; k <= cur_acc; ++k)
                     prev_acc.push(accumulators[k]);
                  // for non-greedy repeats save whether we have a match already:
                  if(static_cast<const re_repeat*>(ptr)->greedy == false)
                  {
                     prev_acc.push(match_found);
                     match_found = false;
                  }
               }
            }
            ptr = static_cast<const re_repeat*>(ptr)->alt.p;
            continue;
         }

         // otherwise see if we can take the repeat:
         if(((unsigned int)accumulators[cur_acc] < static_cast<const re_repeat*>(ptr)->max)
               && access::can_start(*first, static_cast<const re_repeat*>(ptr)->_map, mask_take) &&
               ((first != start_loop[cur_acc]) || !accumulators[cur_acc]))
         {
            // move to next item in list:
            ++accumulators[cur_acc];
            ptr = ptr->next.p;
            start_loop[cur_acc] = first;
            continue;
         }
         else if((first == start_loop[cur_acc]) && accumulators[cur_acc] && ((unsigned int)accumulators[cur_acc] < static_cast<const re_repeat*>(ptr)->min))
         {
            // the repeat was null, and we haven't gone round min times yet,
            // since all subsequent repeats will be null as well, just update
            // our repeat count and skip out.
            accumulators[cur_acc] = static_cast<const re_repeat*>(ptr)->min;
            ptr = static_cast<const re_repeat*>(ptr)->alt.p;
            continue;
         }

         // if we get here then neither option is allowed so fail:
         goto failure;

      }
      case syntax_element_combining:
         if(traits_inst.is_combining(traits_inst.translate(*first, icase)))
            goto failure;
         ++first;
         while((first != last) && traits_inst.is_combining(traits_inst.translate(*first, icase)))++first;
         ptr = ptr->next.p;
         continue;
      case syntax_element_soft_buffer_end:
         {
            if(flags & match_not_eob)
               goto failure;
            iterator p(first);
            while((p != last) && traits_inst.is_separator(traits_inst.translate(*p, icase)))++p;
            if(p != last)
               goto failure;
            ptr = ptr->next.p;
            continue;
         }
      case syntax_element_restart_continue:
         if(first != temp_match[-1].first)
            goto failure;
         ptr = ptr->next.p;
         continue;
      default:
         jm_assert(0); // should never get to here!!
         return false;
      }
   }

   //
   // if we get to here then we've run out of characters to match against,
   // we could however still have non-character regex items left
   if((ptr->can_be_null == 0) && ((flags & match_partial) == 0))
      goto failure;
   while(true)
   {
      jm_assert(ptr);
      ++state_count;
      switch(ptr->type)
      {
      case syntax_element_match:
         goto match_jump;
      case syntax_element_startmark:
         goto start_mark_jump;
      case syntax_element_endmark:
         goto end_mark_jump;
      case syntax_element_start_line:
         goto outer_line_check;
      case syntax_element_end_line:
         // we're at the end so *first is never valid:
         if((flags & match_not_eol) == 0)
         {
            ptr = ptr->next.p;
            continue;
         }
         goto failure;
      case syntax_element_word_boundary:
      case syntax_element_word_end:
         if(((flags & match_not_eow) == 0) && (first != temp_match[0].first))
         {
            iterator t(first);
            --t;
            if(traits_inst.is_class(*t, traits::char_class_word))
            {
               ptr = ptr->next.p;
               continue;
            }
         }
         goto failure;
      case syntax_element_buffer_end:
      case syntax_element_soft_buffer_end:
         if(flags & match_not_eob)
            goto failure;
         // OK match:
         ptr = ptr->next.p;
         break;
      case syntax_element_jump:
         ptr = static_cast<const re_jump*>(ptr)->alt.p;
         continue;
      case syntax_element_alt:
         if(ptr->can_be_null & mask_take)
         {
            // we can test the first alternative,
            // see if we need to push next alternative:
            if(ptr->can_be_null & mask_skip)
            {
               if(need_push_match)
                  matches.push(temp_match);
               for(k = 0; k <= cur_acc; ++k)
                  prev_pos.push(start_loop[k]);
               prev_pos.push(first);
               prev_record.push(ptr);
               for(k = 0; k <= cur_acc; ++k)
                  prev_acc.push(accumulators[k]);
               prev_acc.push(cur_acc);
            }
            ptr = ptr->next.p;
            continue;
         }
         if(ptr->can_be_null & mask_skip)
         {
            ptr = static_cast<const re_jump*>(ptr)->alt.p;
            continue;
         }
         goto failure;  // neither option is possible
      case syntax_element_rep:
         // if we're moving to a higher id (nested repeats etc)
         // zero out our accumualtors:
         if(cur_acc < static_cast<const re_repeat*>(ptr)->id)
         {
            cur_acc = static_cast<const re_repeat*>(ptr)->id;
            accumulators[cur_acc] = 0;
            start_loop[cur_acc] = first;
         }

         cur_acc = static_cast<const re_repeat*>(ptr)->id;

         // see if we can skip the repeat:
         if(((unsigned int)accumulators[cur_acc] >= static_cast<const re_repeat*>(ptr)->min)
            && ((ptr->can_be_null & mask_skip) || (flags & match_partial)))
         {
            // don't push failure info, there's no point:
            ptr = static_cast<const re_repeat*>(ptr)->alt.p;
            continue;
         }

         // otherwise see if we can take the repeat:
         if(((unsigned int)accumulators[cur_acc] < static_cast<const re_repeat*>(ptr)->max)
               && (((ptr->can_be_null & (mask_take | mask_skip)) == (mask_take | mask_skip))) || (flags & match_partial))
         {
            // move to next item in list:
            ++accumulators[cur_acc];
            ptr = ptr->next.p;
            start_loop[cur_acc] = first;
            continue;
         }

         // if we get here then neither option is allowed so fail:
         goto failure;
      case syntax_element_restart_continue:
         if(first != temp_match[-1].first)
            goto failure;
         ptr = ptr->next.p;
         continue;
      case syntax_element_backref:
         if(temp_match[static_cast<const re_brace*>(ptr)->index].first
               != temp_match[static_cast<const re_brace*>(ptr)->index].second)
               goto failure;
         ptr = ptr->next.p;
         continue;
      default:
         goto failure;
      }
   }

   failure:

   //
   // check to see if we've been searching too many states:
   //
   if(state_count >= pd.max_state_count)
   {
#ifndef BOOST_NO_EXCEPTIONS
      throw std::runtime_error("Max regex search depth exceeded.");
#else
      while(matches.empty() == false)
         matches.pop();
      while(prev_pos.empty() == false)
         prev_pos.pop();
      while(prev_record.empty() == false)
         prev_record.pop();
      while(prev_acc.empty() == false)
         prev_acc.pop();
      return false;
#endif
   }

   //
   // check for possible partial match:
   //
   if((flags & match_partial)
      && !match_found          // no full match already
      && (base != first)       // some charcters have been consumed
      && (first == last))      // end of input has been reached
   {
      have_partial_match = true;
      temp_match.set_second(first, 0, false);
      m.maybe_assign(temp_match);
   }

   if(prev_record.empty() == false)
   {
      ptr = prev_record.peek();
      switch(ptr->type)
      {
      case syntax_element_alt:
         // get next alternative:
         ptr = static_cast<const re_jump*>(ptr)->alt.p;
         if(need_push_match)
            matches.pop(temp_match);
         prev_acc.pop(cur_acc);
         for(k = cur_acc; k >= 0; --k)
            prev_acc.pop(accumulators[k]);
         prev_pos.pop(first);
         for(k = cur_acc; k >= 0; --k)
            prev_pos.pop(start_loop[k]);
         prev_record.pop();
         if(unwind_stack) goto failure; // unwinding forward assert
         goto retry;
      case syntax_element_rep:
      {
         // we're doing least number of repeats first,
         // increment count and repeat again:
         bool saved_matched = match_found;
         if(need_push_match)
            matches.pop(temp_match);
         prev_pos.pop(first);
         cur_acc = static_cast<const re_repeat*>(ptr)->id;
         if(static_cast<const re_repeat*>(ptr)->greedy == false)
         {
            saved_matched = prev_acc.peek();
            prev_acc.pop();
         }
         for(k = cur_acc; k >= 0; --k)
            prev_acc.pop(accumulators[k]);
         prev_record.pop();
         if(unwind_stack) goto failure; // unwinding forward assert
         if((unsigned int)++accumulators[cur_acc] > static_cast<const re_repeat*>(ptr)->max)
            goto failure;  // repetions exhausted.
         //
         // if the repeat is non-greedy, and we found a match then fail again:
         if((static_cast<const re_repeat*>(ptr)->greedy == false) && (match_found == true))
         {
            goto failure;
         }
         else if (match_found == false)
            match_found = saved_matched;
         ptr = ptr->next.p;
         start_loop[cur_acc] = first;
         goto retry;
      }
      case syntax_element_startmark:
      {
         bool saved_matched = match_found;
         matches.pop(temp_match);
         match_found = prev_acc.peek();
         prev_acc.pop();
         prev_acc.pop(cur_acc);
         for(k = cur_acc; k >= 0; --k)
            prev_acc.pop(accumulators[k]);
         prev_pos.pop(first);
         for(k = cur_acc; k >= 0; --k)
            prev_pos.pop(start_loop[k]);
         prev_record.pop();
         unwind_stack = false;
         if(static_cast<const re_brace*>(ptr)->index == -1)
         {
            if (saved_matched == false)
               goto failure;
            ptr = static_cast<const re_jump*>(ptr->next.p)->alt.p->next.p;
            goto retry;
         }
         if(static_cast<const re_brace*>(ptr)->index == -2)
         {
            if (saved_matched == true)
               goto failure;
            ptr = static_cast<const re_jump*>(ptr->next.p)->alt.p->next.p;
            goto retry;
         }
         else goto failure;
      }
      case syntax_element_match:
         if(need_push_match)
            matches.pop(temp_match);
         prev_pos.pop(first);
         prev_record.pop();
         if(unwind_stack) goto failure; // unwinding forward assert
         goto retry;
     default:
         jm_assert(0);
         // mustn't get here!!
      }
   }

   if(match_found || have_partial_match)
   {
      pd.state_count = 0;
      return true;
   }

   // if we get to here then everything has failed
   // and no match was found:
   return false;
}