I introduced an incompatibility in regex11 (1.3.3)

>
> Terry Raymond sent me a message that at first confused me:
>>
>> I found a bug in regex11 and traced it back to your change;
>>
>> Regex11 (1.3.1-soops1,reinz)  Development.
>>
>> | matches testString |
>>
>> testString := '15'.
>>
>> matches := OrderedCollection new.
>>
>> '([1-9]|1[0-9])' asRegex
>>
>>                                matchesIn: testString
>>
>>                                do:  [:each |
>>
>>             matches add: each.].
>>
>> matches
>>
>> Your version results in  OrderedCollection ('15')
>>
>> Previous version result   OrderedCollection ('1' '5')
>>
>> Checking against http://regex101.com/ I get global matches
>>
>> 1
>>
>> 5
>>
>
>
> It turns out that in regular language theory the 'alternatives'
> construct does not prefer left branch above right branch (=greedy), but
> that in most popular regex implementations it does prefer the first
> match (=eager).
> I always thought that regex expressions as a whole are meant to be
> greedy and that is why I introduced this patch.
>
> Looking a bit further I found this comparison page:
> http://www.regular-expressions.info/refbasic.html
> The 'Alternation is greedy' entry is about this feature. It turns out
> that I am not alone in my expectations: POSIX ERE, Gnu BRE and Gnu ERE
> also use a greedy implementation while all other libraries listed there
> use the eager variant.
>
> We now have a regex in the field, that is incompatible with the most
> popular regex libraries but that in my opinion creates more predictable
> results.
> For example predict what part of the string will be matched by 'our'
> regex11 vs the regex101.com site in the following case:
>    '.*(ABCD|BC)' asRegex matches: 'fooABCD'
> (no cheating: first predict, then try :-)
>
> I like this predictability so I would like to keep it in, but it may
> turn out to be a major PITA when porting regexen from other languages.
>
> What is your opinion, should this fix be rolled back or should we keep it?
>
>
> Reinout Heeck
> --------------------
> [hidden email]

> Hi Reinout,
>
> Much as I agree with your intuition, I believe you should roll back
> this change.
>
> The reason the 'old' result is correct is that '.*' is also greedy. In
> your example matching 'fooABCD' it is '.*' that is consuming as many
> characters as possible before moving on to the bracketed expression.
> The greediness (or not) of the alternation never comes into play.
>

> On 6/11/2014 4:07 PM, Anthony Lander wrote:
>> Hi Reinout,
>>
>> Much as I agree with your intuition, I believe you should roll back
>> this change.
>>
>> The reason the 'old' result is correct is that '.*' is also greedy. In
>> your example matching 'fooABCD' it is '.*' that is consuming as many
>> characters as possible before moving on to the bracketed expression.
>> The greediness (or not) of the alternation never comes into play.
>>
> The greediness as I implemented it at the time is not computed as a
> local measure (maximum amount of characters matched by an alternation)
> but as a global measure (which branch of the alternation advances the
> matching process the furthest).
>
> With that interpretation the greediness/eagerness of the alternation
> does come into play.
> (and then both are 'correct')
>
>
> Anyway, so far we see one vote for rollback and one suggestion to add a
> switch...

> Initial sketch, it seems to work but is mostly untested!
>
> TODO:
> --documentation
> --tests
>
> This initial version implements eager semantics for RxmBranch:
>
> | matches |
> matches := OrderedCollection new.
> '([1-9]|1[0-9])' asPopularRegex matchesIn: '15
>     do: [:each | matches add: each].
> matches "-> OrderedCollection ('1' '5')"
>
> | matches  |
> matches := OrderedCollection new.
> '.*(ABCD|BC)' asPopularRegex matchesIn: 'fooABCD'
>     do: [:each | matches add: each].
> matches -> "OrderedCollection ('fooABC')"

> Initial sketch, it seems to work but is mostly untested!
>
> TODO:
> --documentation
> --tests
>
> This initial version implements eager semantics for RxmBranch:
>
> | matches |
> matches := OrderedCollection new.
> '([1-9]|1[0-9])' asPopularRegex matchesIn: '15
>     do: [:each | matches add: each].
> matches "-> OrderedCollection ('1' '5')"
>
> | matches  |
> matches := OrderedCollection new.
> '.*(ABCD|BC)' asPopularRegex matchesIn: 'fooABCD'
>     do: [:each | matches add: each].
> matches -> "OrderedCollection ('fooABC')"

> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On
> Behalf Of Reinout Heeck
> Sent: Thursday, June 12, 2014 6:26 AM
> To: [hidden email]
> Subject: Re: [vwnc] I introduced an incompatibility in regex11 (1.3.3)
>
> (resent from proper list address)
>
> I published the package [Regex11 made popular] into the public repository.
>
> This is the 'switch' that provides semantics more suitable to porting

> in it please take the lead :-)
>
> Blessing comment:
>
> > Initial sketch, it seems to work but is mostly untested!
> >
> > TODO:
> > --documentation
> > --tests
> >
> > This initial version implements eager semantics for RxmBranch:
> >
> > | matches |
> > matches := OrderedCollection new.
> > '([1-9]|1[0-9])' asPopularRegex matchesIn: '15
> >     do: [:each | matches add: each].
> > matches "-> OrderedCollection ('1' '5')"
> >
> > | matches  |
> > matches := OrderedCollection new.
> > '.*(ABCD|BC)' asPopularRegex matchesIn: 'fooABCD'
> >     do: [:each | matches add: each].
> > matches -> "OrderedCollection ('fooABC')"
>
>
> Hope this helps,
>
> Reinout
> -------
> _______________________________________________
> vwnc mailing list
> [hidden email]
> http://lists.cs.uiuc.edu/mailman/listinfo/vwnc

> (1) =============
> regex101.com
> expression:    /([1-9]|1[0-9])/g
> test: 15
> globally matches:    '15'
> match groups: '1','5'
>
> '([1-9]|1[0-9])' asPopularRegex matchesIn: '15' "--> OrderedCollection
> ('1' '5')"
> |rs matchedGroups|
> rs := '15' readStream. matchedGroups := OrderedCollection new.
> [rs atEnd] whileFalse:[
>     matchedGroups add: ('([1-9]|1[0-9])' asPopularRegex searchStream:
> rs; subexpressions: 2)].
> matchedGroups "--> OrderedCollection (#('1') #('5'))"
> --> this seems consistent
>
> (2) =============
> regex101.com
> expression    /([1-9]|1[0-9])/
> test 15
> globally matches:    '1'
> match groups: '1'
>
> ('([1-9]|1[0-9])' asPopularRegex matchesIn: '15') first "--> '1' "
> '([1-9]|1[0-9])' asPopularRegex search: '15'; subexpressions: 2 "-->
> #('1') "
> --> this seems consistent
>
> (3) =============
> regex101.com
> expression:    /.*(ABCD|BC)/g
> test: fooABCD
> globally matches:    'fooABC'
> match groups: 'BC'
>
> '.*(ABCD|BC)' asPopularRegex matchesIn: 'fooABCD' "-->
> OrderedCollection ('fooABC')"
> |rs matchedGroups|
> rs := 'fooABCD' readStream. matchedGroups := OrderedCollection new.
> [rs atEnd] whileFalse:[
>     matchedGroups add: ('.*(ABCD|BC)' asPopularRegex searchStream: rs;
> subexpressions: 2)].
> matchedGroups "--> OrderedCollection (#('BC') #()) "
> --> this seems consistent
>
> (4) =============
> regex101.com
> expression    /.*(ABCD|BC)/
> test fooABCD
> globally matches:    'fooABC'
> match groups: 'BC'
>
> ('.*(ABCD|BC)' asPopularRegex matchesIn: 'fooABCD') first "--> 'fooABC' "
> '.*(ABCD|BC)' asPopularRegex search: 'fooABCD'; subexpressions: 2 "-->
> #('BC') "
> --> this seems consistent

> [...]
>
>
> What is also interesting is that for regexPopular
>    '.*(ABCD|BC)' asRegex matches: 'fooABCD'
> true
>    '.*(ABCD|BC)' asPopularRegex matches: 'fooABCD'
> false
>
> How is it that asPopuluarRegex matches is false but for global matches
> it returns a match?