buggrep - Bugs: bug #12210, EGexecute() fails to find matches...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #12210: EGexecute() fails to find matches on (exact && match_icase)

Submitter:  None
Submitted:  Fri 04 Mar 2005 11:41:17 AM UTC
   
 
Category:  None Severity:  3 - Normal
Item Group:  None Status:  Need Info
Privacy:  Public Assigned to:  None
Open/Closed:  Closed

Jump to the original submission

Fri 04 Dec 2009 07:41:48 PM UTC, comment #14: 

Messy report, but the fix seems to be there.

Paolo Bonzini <bonzini>
Sat 05 Mar 2005 07:27:26 PM UTC, comment #13: 


>We're wasting our time.


I learned more about grep, so can't say.

>This is already covered by Red Hat's "grep-2.5.1-oi.patch".


The patch addresses the problem perfectly. I think it should go in. Please just consider that patch #3767 depends on grep-2.5.1-oi.patch.

Claudio

Claudio Fontana <sick_soul>
Sat 05 Mar 2005 06:01:53 PM UTC, comment #12: 

MB_CUR_MAX depends on LC_ALL (or equivalent) and indeed it does not work with LC_ALL=C or LC_ALL=en_US.iso88591, yet it does with LC_ALL=en_US.UTF-8.

We're wasting our time.  This is already covered by Red Hat's "grep-2.5.1-oi.patch".  I had not noticed it had not yet been incorporated in CVS.  It's available from
  :pserver:anonymous@cvs.fedora.redhat.com:/cvs/dist
  devel/grep/grep-2.5.1-oi.patch
and
  <http://cvs.fedora.redhat.com/viewcvs/devel/grep/>.

It seems it's in glibc since 2002-02-26:
<http://sourceware.org/cgi-bin/cvsweb.cgi/libc/posix/regex.h.diff?r1=1.23&r2=1.24&cvsroot=glibc&f=h>.

Ok to close this bug?

Charles Levert <charles_levert>
Sat 05 Mar 2005 05:32:13 PM UTC, comment #11: 

I might have been too cryptic.

The for .. tolower loop is "required" when not using multibyte strings (MBS_SUPPORT = 0 or MB_CUR_MAX = 1), and mimics the for .. towlower loop in check_multibyte_string().

The reason I discovered today is that in Gcompile we are not calling the regex external api (regcomp) passing the REG_ICASE in the cflags, but we're calling re_compile_pattern internal function directly.

This way we are skipping the code in regex.c which deals with REG_ICASE at the beginning of regcomp.

There are two solutions I see:

1) assign to the translate member directly (as I have done in the patch), but fix it to do it only if not using multibyte strings (as speedup). Downside: no guarantee that will work in the future, as it is not something regex exposes.

2) redesign the entire thing to use the documented regex interfaces.

I would suggest going 1) for the short term, and 2) as a long term goal.

I will fix my patch to avoid doing the unnecessary assignment to translate when using multibyte strings.

I know my patch is far too big (it was not intended primarily for this goal), I will prepare a more focused one when I have it fixed.


Anonymous
Sat 05 Mar 2005 12:47:05 PM UTC, comment #10: 

Ok, I hope I got it.
Since it is not appearing in config.h, could you give me your value for MBS_SUPPORT and MB_CUR_MAX?

I have MBS_SUPPORT 1 and MB_CUR_MAX 1

If you have MB_CUR_MAX > 1 it's solved I think.
See search.c:358

Claudio

Claudio Fontana <sick_soul>
Sat 05 Mar 2005 07:07:44 AM UTC, comment #9: 


> great...but where's the color?


It's there for me.

> [nomatch]


Matches for me.

I am using
  bash$ gcc --version
  gcc (GCC) 3.3.2 20031022 (Red Hat Linux 3.3.2-1)
and
  bash$ rpm -q glibc
  glibc-2.3.2-101.4
on Linux 2.4 and I have attached the config.h file produced by CVS grep's configure on my system.  Please do so with yours.  Also, I have used
  "./configure --verbose --without-included-regex".

I will look at your linked patch, but let's please work on finding the problem on a minimally modified latest CVS version first.  By minimally modified, I mean only with modifications that pertain to zeroing-in on that specific problem.

Charles Levert <charles_levert>
Fri 04 Mar 2005 11:15:29 PM UTC, comment #8: 

Hello,

> > grep.c::prline()
>
> The prline() problem where the case-folded match
> instead of the original is
> printed is known.  I advocate getting rid of the
> whole thing in patch #3767
> as it's no longer needed anyways (unless you can
> prove otherwise).


Well, ok we both agree that those should be removed,
and I looked at patch #3767 (got the .c), and it would
work ok if not for the problem I am trying to explain
:)

Try to apply your patch, build, then type:

$ echo Claudio | ./grep -i --color claudio
Claudio

great...but where's the color?

$ Try also:
echo Claudio | ./grep -i -o claudio

[nomatch]

 - Sorry about my name being everywhere :P

This is exactly the point I am making..
your patch SHOULD work, but does not due to a problem
internal to EGexecute when called with exact=1 or one
of the called functions / related state. At least this is what happens on my box.

I have tried to address the issue among others in a
patch I am preparing.

Note that I did exactly just like you removing the
special (match_icase) treatment, but then observing it
does not work in match_icase cases, I hit my head
against the monitor studying the thing and did NOT
come out with a solution, mainly because I still don't
get the various involved regex internals. Given enough
time, I hope to learn it all.

I looked at another person's patch (cannot remember
anymore, called something like javaed, could have been
unrelated), and noticed he assigned to
patterns[pcount].regexbuf.translate . So I supposed I
could do once and for all at the start of program a

if (match_icase)
  build_translation_table(); /* with a for..TOLOWER() */

/* and then when adding a pattern */

if (match_icase)
patterns[pcount].regexbuf.translate =
icase_trans_table;

It seems to work nicely, however I do not know if
there are issues about wide char strings (I do not
have wide char strings support compiled in, never programmed using them -still using LANG=C and ASCII7 files-). To
build the translation table I am using TOLOWER macro.

Maybe you could help me by making it work with wc
strings too?

The patch in question is contained in this:

http://cmdftp.sourceforge.net/preview.p1.patch

You could find some variable names changed, however you
should be able to figure out by looking at grepopt.h

Claudio


Claudio Fontana <sick_soul>
Fri 04 Mar 2005 09:37:35 PM UTC, comment #7: 


> I'm not considering wide char issues here.


Note that wide char support might be there and its functions used even if the pattern and files are plain ASCII.  Preliminary case-folding is only needed or performed when it's there.

> grep.c::prline()


The prline() problem where the case-folded match instead of the original is printed is known.  I advocate getting rid of the whole thing in patch #3767 as it's no longer needed anyways (unless you can prove otherwise).  The printing problem is simple:  in the "only-matching && match_icase" code path of prline(), b should be set to "beg + ...", not "ibeg + ...", just as it is in its other match_icase code path.

> a new design...


Yes, an interface similar to that of pcre.  Mainly for the ability to be able to say either "same string but next match" or "same string but starting at char offset i instead of 0" (for the ^pattern and \<pattern bug when multiple matches per line are involved).  Similar to \G in Perl or -start in Tcl.

> I was hoping to help the grep community


That's always appreciated.

[Side note:  please create yourself a Savannah account and log in for posting so that we can know who you are, especially since in your case I would have recognized you from the bug-grep mailing list and known of your familiarity with the code.]

Charles Levert <charles_levert>
Fri 04 Mar 2005 08:27:58 PM UTC, comment #6: 

I'm using latest (today's) CVS.
For a short example of a consequence look at bug #9768
I'm not considering wide char issues here.

Detailed description of what I see as the root problem (design problems involving EGexecute with exact=1) follows.

Disclaimer: I have studied the grep source quite hard, but only for a few days and I am still struggling with dfa, kwset and regex internals. Please do not shoot. This mail is long.

involved globals:
match_icase && only_matching

mainly involved functions:
grep.c::prline()
search.c::EGexecute() and called functions

command: echo Claudio | grep -io claudio
output: claudio
expected output: Claudio

description:
after compiling the pattern (Gcompile), we reach grepfile(), then grep(), then grepbuf().
In grepbuf() we have the call to execute (in our case EGexecute), called with last parameter 0 (non exact), and on the buffer containing "Claudio". We are looking for matching lines, but do not care about offset of the match in the line yet.

Ok, EGexecute finds the match easily, because we succeed using the first strat (kwset). The position of the matching line (0) in the buffer is returned.

Back to grepbuf(), we now enter in prtext() since we found a match, and from prtext() to prline().

Now the nasty prline, in all the cases involving match_icase  and either color_option or only_matching, needs to search again in the string, this time with exact=1 (we need the actual offset in the line), because we want to be able to mark before|match|after for output purposes.

The nasty prline, for all cases about match_icase says:

if (match_icase)
{
/* cut */
    for (i = 0; i < lim - beg; i++)
      ibeg[i] = tolower (beg[i]);

      /* do_stuff involving execute() passing exact = 1
         calc ing on the NEW buffer,
         but also printing from the NEW buffer */
}

Now why is the buffer being converted to lower case before calling execute() (EGexecute()) with exact = 1?

I think that the answer is, because EGexecute fails to consider icase when passed with exact=1 and cases differ. If this is wanted, it looks very evil to me.

So the hack has been written around it, which mostly works, but helps making the prline function the blob it is, and causing the damage of messing the output in the only_matching case.

I think that at first the search.c function EGexecute() exact=1 case should be fixed, to make it work even in the match_icase situation without having to tolower all the data before calling it.

I think that as long term goal, a new design for the exact case should be found. Bug #11579 for example is involved, very difficult to fix (in a clean way) with current exact case design imo.

I was hoping to help the grep community, so please if I missed something obvious, help me understand.

Thanks

CLaudio

Anonymous
Fri 04 Mar 2005 07:38:00 PM UTC, comment #5: 

I'm not sure if we should care about memory leaks, as there are already some and *compile is only called once from src/grep.c, but here's a third version of the patch.

Charles Levert <charles_levert>
Fri 04 Mar 2005 07:07:10 PM UTC, comment #4: 

I think I didn't correctly understand the part this begin an internal-only API thing in my last post.

Would the attached patch solve your problem?

Charles Levert <charles_levert>
Fri 04 Mar 2005 06:22:04 PM UTC, comment #3: 

There is a twlower() call for this in check_multibyte_string() in src/search.c.  That's only used if defined(MBS_SUPPORT), if (MB_CUR_MAX > 1), and if match_icase.  That mirrors what is initially done to the pattern in src/grep.c.

Maybe what's done to the pattern should be moved to the *compile functions in src/search.c for symmetry.

The only other condition that triggers the call to check_multibyte_string() is if kwset.

I still would like to be able to reproduce the bug.  Sorry to ask again, but are you using latest CVS (more recent than at the very least src/search.c version 1.30, 2004/12/16 07:18:15)?  Can you produce a test case shell script that should fail when I try it?

Charles Levert <charles_levert>
Fri 04 Mar 2005 02:50:15 PM UTC, comment #2: 

Using CVS.
Sorry for the confusion that may arise, the bug is not visible because it's in the API that search.c exposes to grep.c .

Since EGexecute() is not able to find matches when the passed 'exact' parameter is set and match_icase is set (and buffer and pattern differ in case), an ugly workaround exists in grep.c, where the line is converted to lower case on the fly before calling EGexecute. This conversion however causes other problems with --only-matching and is not the right place to solve it.

The problem should be solved in search.c.
I am investigating patch #1940 that might hold part of the solution.

Additional contribution to understanding the issue would be welcome.

Anonymous
Fri 04 Mar 2005 01:24:33 PM UTC, comment #1: 

Which version of GNU grep are you using?  This may already have been fixed.  It works for me on the CVS version.  Only --color but not --only-matching works on an older (not latest) Red Hat version based on 2.5.1.

Charles Levert <charles_levert>
Fri 04 Mar 2005 11:41:17 AM UTC, original submission:  

This bug causes problems with --color and --only-matching when paired with --ignore-case.

EGexecute() in search.c fails to find 'exact' matches differing in case when match_icase has been set.

See also bug #9768

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attached Files
file #2675:  config.h.charles0 added by charles_levert (10KiB - application/octet-stream - Produced by my CVS grep's configure.)
file #2673:  search.c.icase+memleaks.patch added by charles_levert (4KiB - text/x-patch - Same, fixes other memory leaks, simpler free() logic.)
file #2669:  search.c.icase.patch added by charles_levert (3KiB - text/x-patch - Same, frees copy of initial mb pointer.)
file #2668:  search.c.icase.patch added by charles_levert (3KiB - text/x-patch - Same, without memory leaks.)
file #2667:  search.c.icase.patch added by charles_levert (3KiB - text/x-patch - Unidiff patch to add check_multibyte_pattern() to src/search.c)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by bonzini (Posted a comment)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2009-12-04 bonzini Open/ClosedOpen Closed
    2005-03-05 charles_levert Attached File- Added config.h.charles0, #2282
    2005-03-04 charles_levert Attached File- Added search.c.icase+memleaks.patch, #2280
    2005-03-04 charles_levert Attached File- Added search.c.icase.patch, #2276
    2005-03-04 charles_levert Attached File- Added search.c.icase.patch, #2275
    2005-03-04 charles_levert Attached File- Added search.c.icase.patch, #2274
    2005-03-04 charles_levert StatusNone Need Info

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code