Tcl Source Code

View Ticket
Login
Ticket UUID: 3574242
Title: exact match is greedy by reluctant exact match quantifier
Type: Bug Created on: 2012-10-03 22:30:52
Submitter: sebres Assigned to: sebres
Subsystem: 43. Regexp Severity: Minor
Priority: 7 High Last modified: 2019-11-22 20:24:39
Status: Open Closed by: nobody
Resolution: None Closed on:
Version: None
Description:
Possible bug, cause IMO that should match the same:
Or a documentation bug - according to documentation "{m}?" is ungreedy quantifier.

% regexp -inline {((?:ab|abc){1}?)(cd|d){1}?} abcd
abcd abc d
% regexp -inline {((?:ab|abc){1,1}?)(cd|d){1,1}?} abcd
abcd ab cd
User Comments:
sebres added on 2019-11-22 14:52:40:

A fresh concern regarding the issue and new findings after discussion in tclchat with pooryorick.

The issue could be explained with following sentence from the documentation:

A quantified atom with quantifier {m} or {m}? has the same preference (possibly none) as the atom itself. A quantified atom with other normal quantifiers (including {m,n} with m equal to n) prefers longest match. A quantified atom with other non-greedy quantifiers (including {m,n}? with m equal to n) prefers shortest match.

But the fact that {m,n} prefers the shortest match doesn't mean that the sub-expression it is applied to should prefer the shortest match (at least, it doesn't necessarily mean that).


Another interesting set of examples which can be related to the same issue:

    % regexp -inline {(t*?)?} ttt
    ttt ttt
    % regexp -inline {(t*)?} ttt
    ttt ttt
Although it behaves like described in the documentation:
A branch has the same preference as the first quantified atom in it which has a preference. An RE consisting of two or more branches connected by the | operator prefers longest match.

But it does not explain why the group is expanded to the whole match, as well as the difference to this counter-example:

    % regexp -all -inline {(t)*} ttt
    ttt t

So the change to greedy quantifier of RE seems to affect capturing behavior of (initially) non-greedy group, compared to (initially) greedy group.


FWIW, maybe following would explain the reason (or rather the necessity) why or for which cases the sub-branch (group) could be non-greedy (why this can be expected or used):

    % regexp -inline {(t*?(\w+))?} ttxx
    ttxx ttxx ttxx
    % regexp -inline {(t*(\w+))?} ttxx
    ttxx ttxx xx
But that all still don't explain the growth of captured non-greedy group to the whole match.


sebres added on 2019-11-22 17:13:34:

If the issue is "caused" because RE-engine following main rule "greediness of topmost expression wins" or like a Kevin's statement:

A general rule is that the greediness of the outermost quantifier determines the greediness of everything in the subexpression.

it could explain why initially non-greedy subexpression grows, even to fulfill the whole match be greedy.

So for example here the first capturing group grows to whole match, the second (inner) group capturing aaaf and aaf each after other (so ultimately gets the value of the last one).

    % regexp -inline {((a*f)*?)?} aaafaaf
    aaafaaf aaafaaf aaf

But there is just another example illustrating that this "concept" is not completely correct:

    % regexp -inline {((a*f)*?)*} aaafaaf
    aaafaaf aaf aaf
    % regexp -inline {((a*f)*?)+} aaafaaf
    aaafaaf {} {}

Both of topmost quantifiers (red/green) are greedy, the whole expression is greedy.
The whole result corresponds greedy whole match (matches the whole string in both cases).
But in the second case the groups are empty (so it is somehow non-greedy anymore).

So the (more aggressive) quantifier + behaves fewer greedy as (fewer aggressive) quantifier * inside the capturing groups.


sebres added on 2019-11-22 20:24:39:

After pretty productive discussion in tclchat with Andrew Gierth (RhodiumToad) we have new other findings now.

The new handling of quantifier "+" (in contrary to "*") as well as "{1,}" (in contrary to "{0,}") makes impossible to retrieve indices of last successful matched capturing groups, which results to impossibly to differentiate which sub-group (expression) causes the match exactly.

I hope following example would illustrate that:

    % regexp -indices -inline {((a?)*|(b?)*)*} aaa
    {0 2} {0 2} {2 2} {-1 -1}
    % regexp -indices -inline {((a?)*|(b?)*)+} aaa
    {0 2} {3 2} {-1 -1} {-1 -1}

So it is basically impossible to differentiate which of last child sub-group (a?)* or (b?)* caused a match of the parent (which is also mistakenly an empty match outside of string - {3 2}), as well as the to retrieve the last indices for that, because both are {-1 -1}, if "+" quantifier was used in some parent expression.

The same is valid for this (note the "*" instead of "?" in both last nesting groups):

    % regexp -indices -inline {((a*)*|(b*)*)*} aaa
    {0 2} {0 2} {0 2} {-1 -1}
    % regexp -indices -inline {((a*)*|(b*)*)+} aaa
    {0 2} {3 2} {-1 -1} {-1 -1}

Either one would expect the same result as using "*" instead of "+" here.
Or if the decision is sub-expression matches empty string, the indices shall be still inside the parent (empty but not outside), so we should get something like this for both cases with "+" quantifier:

    % regexp -indices -inline {((a?)*|(b?)*)+} aaa
    % regexp -indices -inline {((a*)*|(b*)*)+} aaa
    {0 2} {2 1} {2 1} {-1 -1}

Andrew is also going to file this as a Postgres bug...
Here is the issue in PG.