Regexp: capturing groups in repetitions

[verdyp]

BPO	7132
Nosy	@ezio-melotti, @davidchambers

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2009-10-14.20:08:14.901>
labels = ['type-feature', 'library']
title = 'Regexp: capturing groups in repetitions'
updated_at = <Date 2014-03-22.23:46:07.052>
user = 'https://bugs.python.org/verdyp'

bugs.python.org fields:

activity = <Date 2014-03-22.23:46:07.052>
actor = 'BreamoreBoy'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2009-10-14.20:08:14.901>
creator = 'verdy_p'
dependencies = []
files = []
hgrepos = []
issue_num = 7132
keywords = []
message_count = 27.0
messages = ['94022', '94025', '94029', '94030', '94034', '94038', '94040', '94043', '94045', '94046', '94047', '94049', '94050', '94051', '94053', '94056', '94057', '94058', '94060', '94065', '94066', '94067', '94068', '94071', '102080', '121484', '214523']
nosy_count = 5.0
nosy_names = ['ezio.melotti', 'mrabarnett', 'verdy_p', 'davidchambers', 'BreamoreBoy']
pr_nums = []
priority = 'low'
resolution = 'rejected'
stage = 'resolved'
status = 'languishing'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue7132'
versions = ['Python 3.2']

[verdyp]

For now, when capturing groups are used within repetitions, it is impossible to capure what they match
individually within the list of matched repetitions.

E.g. the following regular expression:

(0|1[0-9]{0,2}|2(?:[0-4][0-9]?|5[0-5]?)?)(?:\.(0|1[0-9]{0,2}|2(?:[0-4][0-9]?|5[0-5]?)?)){3}

is a regexp that contains two capturing groups (\1 and \2), but whose the second one is repeated (3 times) to
match an IPv4 address in dotted decimal format. We'd like to be able to get the individual multiple matchs
for the second group.

For now, capturing groups don't record the full list of matches, but just override the last occurence of the
capturing group (or just the first if the repetition is not greedy, which is not the case here because the
repetition "{3}" is not followed by a "?"). So \1 will effectively return the first decimal component of the
IPv4 address, but \2 will just return the last (fourth) decimal component.

I'd like to have the possibility to have a compilation flag "R" that would indicate that capturing groups
will not just return a single occurence, but all occurences of the same group. If this "R" flag is enabled,
then:

• the Match.group(index) will not just return a single string but a list of strings, with as many occurences
  as the number of effective repetitions of the same capturing group. The last element in that list will be the
  one equal to the current behavior

• the Match.start(index) and Match.end(index) will also both return a list of positions, those lists having
  the same length as the list returned by Match.group(index).

• for consistency, the returned values as lists of strings (instead of just single strings) will apply to all
  capturing groups, even if they are not repeated.

Effectively, with the same regexp above, we will be able to retreive (and possibily substitute):

• the first decimal component of the IPv4 address with "{\1:1}" (or "{\1:}" or "{\1}" or "\1" as before),
  i.e. the 1st (and last) occurence of capturing group 1, or in Match.group(1)[1], or between string positions Match.start(1)[1] and Match.end(1)[1] ;

• the second decimal component of the IPv4 address with "{\2:1}", i.e. the 1st occurence of capturing group
  2, or in Match.group(2)[1], or between string positions Match.start(2)[1] and Match.end(2)[1] ;

• the third decimal component of the IPv4 address with "{\2:2}", i.e. the 2nd occurence of capturing group 2,
  or in Match.group(2)[2], or between string positions Match.start(2)[2] and Match.end(2)[2] ;

• the fourth decimal component of the IPv4 address with "{\2:3}" (or "{\2:}" or "{\2}" or "\2"), i.e. the 3rd
  (and last) occurence of capturing group 2, or in Match.group(2)[2], or between string positions
  Match.start(2)[3] and Match.end(2)[3] ;

This should work with all repetition patterns (both greedy and not greedy, atomic or not, or possessive), in
which the repeated pattern contains any capturing group.

This idea should also be submitted to the developers of the PCRE library (and Perl from which they originate,
and PHP where PCRE is also used), so that they adopt a similar behavior in their regular expressions.

If there's already a candidate syntax or compilation flag in those libraries, this syntax should be used for
repeated capturing groups.

[verdyp]

I'd like to add that the same behavior should also affect the span(index)
method of MatchObject, that should also not just return a single (start,
end) pair, but that should in this case return a list of pairs, one for
each occurence, when the "R" compilation flag is specified.

This also means that the regular expression compilation flag R should be
supported as these constants:
Regexp.R, or Regexp.REPETITIONS

[verdyp]

Rationale for the compilation flag:

You could think that the compilation flag should not be needed. However,
not using it would mean that a LOT of existing regular expressions that
already contain capturing groups in repetitions, and for which the
caputiring group is effectively not used and should have been better
encoded as a non-capuring group like (?:X) instead of (X), will suffer a
negative performance impact and a higher memory usage.

The reason is that the MatchObject will have to store lists of
(start,end) pairs instead of just a single pair: using a list will not
be the default, so MatchObject.group(groupIndex),
MatchObject.start(groupIndex), MatchObject.end(groupIndex), and
MatchObject.span(groupIndex) will continue to return a single value or
single pair, when the R compilation flag is not set (these values will
continue to return only the last occurence, that will be overriden after
each matched occurence of the capturing group.

The MatchObject.groups() will also continue to return a list of single
strings without that flag set (i.e. a list of the last occurence of each
capturing group). But when the R flag will be specified, it will return,
instead, a list of lists, each element being for the group with the same
index and being itself a list of strings, one for each occurence of the
capturing group.

[verdyp]

Implementation details:

Currently, the capturing groups behave quite randomly in the values returned by MachedObject, when backtracking occurs in a repetition. This
proposal will help fix the behavior, because it will also be much easier
to backtrack cleanly, occurence by occurence, by just dropping the last
element in the list of (start,end) pairs stored in the MatchedObject for
all capturing groups specified WITHIN the repeated sub-expression.

[ezio-melotti]

I'm skeptical about what you are proposing for the following reasons:

1. it doesn't exist in any other implementation that I know;
2. if implemented as default behavior:
   • it won't be backward-compatible;
   • it will increase the complexity;
3. it will be a proprietary extension and it will reduce the
   compatibility with other implementations;
4. I can't think to any real word situation where this would be really
   useful.

Using a flag like re.R to change the behavior might solve the issue 2),
but I'll explain why I don't think this is useful.

Let's take a simpler ipv4 address as example: you may want to use
'^(\d{1,3})(?:\.(\d{1,3})){3}$' to capture the digits (without checking
if they are in range(256)).
This currently only returns:
>>> re.match('^(\d{1,3})(?:\.(\d{1,3})){3}$', '192.168.0.1').groups()
('192', '1')

If I understood correctly what you are proposing, you would like it to
return (['192'], ['168', '0', '1']) instead. This will also require an
additional step to join the two lists to get the list with the 4 values.

In these situations where some part is repeating, it's usually easier to
use re.findall() or re.split() (or just a plain str.split for simple
cases like this):
>>> addr = '192.168.0.1'
>>> re.findall('(?:^|\.)(\d{1,3})', addr)
['192', '168', '0', '1']
>>> re.split('\.', addr) # no need to use re.split here
['192', '168', '0', '1']

In both the examples a single step is enough to get what you want
without changing the existing behavior.

'^(\d{1,3})(?:\.(\d{1,3})){3}$' can still be used to check if the string
has the right "format", before using the other methods to extract the data.

So I'm -1 about the whole idea and -0.8 about an additional flag.
Maybe you should discuss about this on the python-ideas ML.

[verdyp]

You're wrong, it WILL be compatible, because it is only conditioned by a
FLAG. The flag is there specifically for instructing the parser to
generate lists of values rather than single values.

Without the regular compilation flag set, as I said, there will be NO
change.

Reopening the proposal, which is perfectly valid !

[verdyp]

Note that I used the IPv4 address format only as an example. There are
plenty of other more complex cases for which we really need to capture the
multiple occurences of a capturing group within a repetition.

I'm NOT asking you how to parse it using MULTIPLE regexps and functions.
Of course you can, but this is a distinct problem, but certinaly NOT a
general solution (your solution using split() will NOT work with really A
LOT of other regular expressions).

[verdyp]

In addition, your suggested regexp for IPv4:

'^(\d{1,3})(?:\.(\d{1,3})){3}$'

is completely WRONG ! It will match INVALID IPv4 address formats like
"000.000.000.000". Reread the RFCs... because "000.000.000.000" is
CERTAINLY NOT an IPv4 address (if it is found in an URL) but a domain name
that must be resolved into an IP address using domain name resolution
requests.

[verdyp]

Summary of your points with my responses :

1. it doesn't exist in any other implementation that I know;

That's exactly why I proposed to discuss it with the developers of other
implementations (I cited PCRE, Perl and PHP developers, there are
others).

2. if implemented as default behavior:

• it won't be backward-compatible;

Wrong. This does not even change the syntax of regualr expressions
themselves.

• it will increase the complexity;

Wrong. All the mechanic is already implemented: when the parser will
store string index positions for a matched group it will just have to
append a pair in the list stored in MatchObject.group(index) (it will
create the list if it is not ealready there, but it should be already
initialized to an empty list by the compiler) when the flag.R is set,
instead of overwriting the existing pair without wondering if there was
already another occurence of the same capturing group.

3. it will be a proprietary extension and it will reduce the
   compatibility with other implementations;

Already suggested above. This will hovever NOT affect the compatibility
of existing implementation that don't have the R flag.

4. I can't think to any real word situation where this would be really
   useful.

There are really a lot ! Using multiple split operations and multiple
parsing on partly parsed regular expressions will not be a solution in
many situations (think about how you would perform matches and using
them that in 'vi' or 'ed' with a single "s/regexp/replacement/flag"
instruction, if there's no extension with a flag and a syntax for
accesing the individual elements the replacement string).

[verdyp]

And anyway, my suggestion is certainly much more useful than atomic groups
and possessive groups that have much lower use, and which are already
being tested in Perl but that Python (or PCRE, PHP, and most
implementations of 'vi'/'ed', or 'sed') still does not support.

[bitdancer]

If you read what Ezio wrote carefully you will see that he addressed
both of your points: he acknowledged that a flag would solve (2) (but
disagreed that it was worth it), and he said you could use the first
expression to validate the string before using the split to obtain the
data. Doing it all in one regex might seem more efficient, but at least
in the single use case you have presented it would lead to more
complicated code.

Simple. obvious feature requests can be opened and acted upon directly
in the tracker, but more complicated requests should be made as
proposals on the python-ideas list, and if they are well received there
then an issue can be opened (or in this case you could reopen this one)
in the tracker with a pointer to the python-ideas thread. In most
cases, such an issue would need to include a proposed patch.

Note that we don't really have a resolution that says 'sent to
python-ideas', thus the use of the 'rejected' status.

[bitdancer]

Just to clarify, when I said "in most cases such an issue would need to
include a proposed patch", I mean that even if everyone agrees it is a
good idea it isn't likely to happen unless there is a proposed patch :)

[verdyp]

I had read carefully ALL what ezio said, this is clear in the fact that
I have summarized my responses to ALL the 4 points given by ezio.

Capturing groups is a VERY useful feature of regular expressions, but
they currently DON'T work as expected (in a useful way) when they are
used within repetitions (unless you don't need any captures at all, for
example when just using find(), and not performing substitutions on the
groups.

My proposal woul have absolutely NO performance impact when capturing
groups are not used (find only, without replacement, so there the R flag
can be safely ignored).

It would also not affect the case where capturing groups are used in the
regexp, but these groups are not referenced in the substitution or in
the code using MatchObject.group(index) : these indexes are already not
used (or should not, because this is most of the time a bug when it just
returns the last occurence).

Using multiple parsing operations with multiple regexps is really
tricky, when all could be done directly from the original regexp,
without modifying it. In addition, using split() or similar will not
work as expected, when the splitting operations will not correctly parse
the context in which the multiple occurences are safely separated (this
context is only correctly specified in the original regexp where the
groups, capturing or not, are specified).

This extension will also NOT affect the non-capturing groups like:
(?:X){m,n}
(?:X)*
(?:X)+
It will ONLY affect the CAPTURING groups like:
(X){m,n}
(X)*
(X)+
and only if the R flag is set (in which case this will NOT affect the
backtracking behavior, or which strings that will be effectively
matched, but only the values of the returned "\n" indexed group.

If my suggestion to keep the existing MatchObject.function(index) API
looks too dangerous for you, because it would change the type of the
returned values when the R flag is set, you can as well rename them to
get a specific occurence of a group. Such as:

 MatchObject.groupOccurences(index)
 MatchObject.startOccurences(index)
 MatchObject.endOccurences(index)
 MatchObject.spanOccurences(index)
 MatchObject.groupsOccurences(index)

But I don't think this is necessary; it will be already expected that
they will return lists of values (or lists of pairs), instead of just
single values (or single pairs) for each group: Python (as well as PHP
or Perl) can already manage return values with varying datatypes.

May be only PCRE (written for C/C++) would need a new API name to return
lists of values instead of single values for each group, due to existing
datatype restrictions.

My proposal is not inconsistant: it returns consistant datatypes when
the R flag is set, for ALL capturing groups (not just those that are
repeated.

Anyway I'll submit my idea to other groups, if I can find where to post
them. Note that I've already implemented it in my own local
implementation of PCRE, and this works perfectly with effectively very
few changes (currently I have had to change the datatypes for matching
objects so that they can return varying types), and I have used it to
create a modified version of 'sed' to perform massive filtering of data:

It really reduces the number of transformation steps needed to process
such data correctly, because a single regexp (exactly the same that is
already used in the first step used to match the substrings we are
interested in, when using existing 'sed' implementations) can be used to
perform the substitutions using indexes within captured groups. And I
would like to have it incoporated in Python (and also Perl or PHP) as
well.