w3ishi's blog

Hello, Mr load:

In this year earlier, I was learn about regular expression and your source code "gnu rx-1.5". Through your idea I wrote my own regular expression lib. But when I learn your source code, I found a bug in it. I sent you a email( lord@gnu.org) about this bug, but no write back, I think you have change your email adress. Today I found your email adress"lord@emf.net", and try whether you can receive my email. The bug detail is for example use this kind of string and pattern:

/////////////////////////////////////////////////////////////////////////////////////
char *string = "@john-doe.i.am.com";
char *pattern = "@([A-Za-z0-9]*)(([\\.\\-]*[a-zA-Z0-9]*)*)\\.([A-Za-z]{2,3})";

// or

char *string = "aaa";
char *pattern = "((a*)*)(\\1)";

The programe may fall in a dead loop. The logical is:
/////////////////////////////////////////////////////////////////////////////////////

case r_concat:
       {
  switch (solns->step)
    {
      enum rx_answers concat_stat;
    case 1:
      solns->split_guess = solns->end;
#if 0
      solns->split_guess = ((solns->end - solns->start) > RX_MANY_CASES
       ? rx_best_end_guess (solns,
              solns->exp->params.pair.left, solns->end)
       : solns->end);
#endif

    concat_split_guess_loop:
      solns->left = rx_make_solutions (solns->regs,
           solns->verse,
           solns->exp->params.pair.left,
           solns->subexps,
           solns->cset_size,
           solns->start,
           solns->split_guess,
           solns->vmfn,
           solns->contextfn,
           solns->closure);
      if (!solns->left)
        {
   solns->step = -1;
   return rx_bogus;
        }
      solns->step = 2;

    case 2:
    concat_try_next_left_match:

      concat_stat = rx_next_solution (solns->left);

      if (concat_stat != rx_yes)
        {
new_tag_i_add:
   rx_free_solutions (solns->left);
   rx_free_solutions (solns->right);
   solns->left = solns->right = 0;
   solns->split_guess = solns->split_guess - 1;
#if 0
   solns->split_guess = ((solns->split_guess - solns->start) > RX_MANY_CASES
           ? rx_best_end_guess (solns,
           solns->exp->params.pair.left,
           solns->split_guess - 1)
           : solns->split_guess - 1);
#endif
   if (solns->split_guess >= solns->start)
     goto concat_split_guess_loop;
   else
     {
       solns->step = -1;
       return concat_stat;
     }
        }
      else
        {
   solns->step = 3;
   /* fall through */
        }

    case 3:
      solns->right = rx_make_solutions (solns->regs,
            solns->verse,
            solns->exp->params.pair.right,
            solns->subexps,
            solns->cset_size,
            solns->split_guess,
            solns->end,
            solns->vmfn,
            solns->contextfn,
            solns->closure);
      if (!solns->right)
        {
   rx_free_solutions (solns->left);
   solns->left = 0;
   solns->step = -1;
   return rx_bogus;
        }

      solns->step = 4;
      /* fall through */

    case 4:
    /* concat_try_next_right_match: */

      concat_stat = rx_next_solution (solns->right);
      if (concat_stat == rx_yes)
        {
   solns->final_tag = solns->right->final_tag;
   return concat_stat;
        }
      else if (concat_stat == rx_no)
        {
   rx_free_solutions (solns->right);
   solns->right = 0;
   solns->step = 2;
   goto concat_try_next_left_match;
        }
      else /*  concat_stat == rx_bogus */
        {
   rx_free_solutions (solns->left);
   solns->left = 0;
   rx_free_solutions (solns->right);
   solns->right = 0;
   solns->step = -1;
   return concat_stat;
        }
    }

 In case 4, if soln->right->start == soln->right->end, and soln->right is not match null, it will go to concat_try_next_left_match,
but if concat_try_next_left_match can match a again the string, it will not solns->split_guess--, so it will come to  concat_stat = rx_next_solution (solns->right); again...
 In my opinion, if case 4 rx_next_solution return rx_no, it have to estimate solns->right->regexp, if it can't nullable and solns->right->start == solns->right->end  goto new_tag_i_add.
 I am a newer in regular expression program, so I don't know if it is a bug? And my English is not good, can you understand me?
 
 A syntax tree may lead error, like this:

              r_concat
              /  \
         r_parens    r_cset
              /
             r_star
             /
            r_parens
            /
           r_concat
           / \
      r_star r_star
          /   \
    r_cset   r_cset

I want join some gnu project, such as http://www.gnuarch.org/revc/index.html, can you give me some idea about how can I start?

Expect your write back, and thank you very much!

 

ShiWei

http://w3ishi.spaces.msn.com

2006-10-20