Bug 876766 - regex fails to follow POSIX on subexpressions
regex fails to follow POSIX on subexpressions
Product: Fedora
Classification: Fedora
Component: glibc (Show other bugs)
Unspecified Unspecified
unspecified Severity unspecified
: ---
: ---
Assigned To: Carlos O'Donell
Fedora Extras Quality Assurance
Depends On:
  Show dependency treegraph
Reported: 2012-11-14 17:19 EST by Eric Blake
Modified: 2016-11-24 10:56 EST (History)
8 users (show)

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Last Closed: 2013-07-04 03:10:48 EDT
Type: Bug
Regression: ---
Mount Type: ---
Documentation: ---
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---

Attachments (Terms of Use)

External Trackers
Tracker ID Priority Status Summary Last Updated
GNU Savannah 37737 None None None Never

  None (edit)
Description Eric Blake 2012-11-14 17:19:01 EST
Description of problem:
POSIX states <http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap09.html>:

> <...> The string matched by a contained subexpression shall be within the
> string matched by the containing subexpression. If the containing
> subexpression does not match, or if there is no match for the contained
> subexpression within the string matched by the containing subexpression, then
> back-reference expressions corresponding to the contained subexpression shall
> not match. <...> For example, <...> the expression "\(a\(b\)*\)*\2" fails to
> match 'abab' <...> .

My read of POSIX is that given the string 'abab', if you let
'\(a\(b\)*\)*' match 'abab', then \2 would also have to match 'b', which
is not present at that point in the string.  Trying successively shorter
options, if you try to match 'aba', then the second occurrence of the
containing subexpression \(a\(b\)*\) has no matches of the contained
subexpression \(b\), so \2 must fail to match.  If you try to match
'ab', then \2 would still have to match 'b'.  If you let \(b\)* match
the null string, then \(a\(b\)*\)* matches 'a'; but in this case, there
is no match for the contained subexpression '\(b\)' within the
containing subexpression, so any attempt to use \2 in that scenario must
fail.  Finally, if you let '\(a\(b\)*\)*' match the null string, then
you again have a case where \(b\) was not matched, so \2 again fails.
So POSIX is right that 'abab' cannot match, no matter how you slice the
string; and therefore glibc has a bug for claiming 'abab' is the match.

Version-Release number of selected component (if applicable):

How reproducible:

Steps to Reproduce:
1. grep --color '\(a\(b\)*\)*\2' <<< abab
2. printf %s 'regexp(abab, \(a\(b\)*\)*\2, \&-\1-\2)' | m4
Actual results:
1. grep outputs 'abab', with all four bytes highlighted as a match
2. m4 outputs 'abab-a-b', showing that the overall expression matched abab, \1 matched 'a' (at character 3), and \2 matched 'b' (at character 2).

Expected results:
1. grep should have no match
2. m4 should output -1 for no match

Additional info:
See also: https://savannah.gnu.org/bugs/?37737
Comment 1 Fedora Admin XMLRPC Client 2013-01-28 15:08:09 EST
This package has changed ownership in the Fedora Package Database.  Reassigning to the new owner of this component.
Comment 2 Fedora End Of Life 2013-07-03 17:16:51 EDT
This message is a reminder that Fedora 17 is nearing its end of life.
Approximately 4 (four) weeks from now Fedora will stop maintaining
and issuing updates for Fedora 17. It is Fedora's policy to close all
bug reports from releases that are no longer maintained. At that time
this bug will be closed as WONTFIX if it remains open with a Fedora 
'version' of '17'.

Package Maintainer: If you wish for this bug to remain open because you
plan to fix it in a currently maintained version, simply change the 'version' 
to a later Fedora version prior to Fedora 17's end of life.

Bug Reporter:  Thank you for reporting this issue and we are sorry that 
we may not be able to fix it before Fedora 17 is end of life. If you 
would still like  to see this bug fixed and are able to reproduce it 
against a later version  of Fedora, you are encouraged  change the 
'version' to a later Fedora version prior to Fedora 17's end of life.

Although we aim to fix as many bugs as possible during every release's 
lifetime, sometimes those efforts are overtaken by events. Often a 
more recent Fedora release includes newer upstream software that fixes 
bugs or makes them obsolete.
Comment 3 Eric Blake 2013-07-03 17:24:28 EDT
This bug is still present in glibc as of the Fedora 19 release: glibc-2.17-11.fc19.x86_64
Comment 4 Paolo Bonzini 2013-07-04 03:10:48 EDT
This is http://sourceware.org/bugzilla/show_bug.cgi?id=52

Note You need to log in before you can comment on or make changes to this bug.