[Bug libstdc++/71500] regex::icase only works on first character in a range

[flashmozzg at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #20 from Danila  ---
Can confirm that it was fixed in 8.1

[Bug libstdc++/71500] regex::icase only works on first character in a range

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

Jonathan Wakely  changed:

   What|Removed |Added

 Status|NEW |RESOLVED
 Resolution|--- |FIXED
   Target Milestone|--- |8.0

--- Comment #19 from Jonathan Wakely  ---
Yes, I think it's all fixed now.

Comment 0 and comment 3 are fixed from 7.1, but comment 15 isn't fixed until
8.1

[Bug libstdc++/71500] regex::icase only works on first character in a range

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

Martin Liška  changed:

   What|Removed |Added

 CC||marxin at gcc dot gnu.org

--- Comment #18 from Martin Liška  ---
Jonathan: Can the bug be marked as resolved? Or please update Known to work.

[Bug libstdc++/71500] regex::icase only works on first character in a range

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #17 from Jonathan Wakely  ---
Author: redi
Date: Tue Sep 19 17:06:12 2017
New Revision: 252981

URL: https://gcc.gnu.org/viewcvs?rev=252981=gcc=rev
Log:
PR libstdc++/71500 restore C++11 compatibility in 

PR libstdc++/71500
* include/bits/regex_executor.tcc
(_Backref_matcher::_M_apply): Use
std::__equal4 instead of C++14 4-iterator overloads of std::equal.
* include/bits/stl_algobase.h (__equal4): New functions implementing
4-iterator overloads of std::equal for use in C++11.
(equal(It1, It1, It2, It2), equal(It1, It1, It2, It2, BinaryPred)):
Move function bodies to new __equal4 functions.
* testsuite/28_regex/simple_c++11.cc: New.

Added:
trunk/libstdc++-v3/testsuite/28_regex/simple_c++11.cc
Modified:
trunk/libstdc++-v3/ChangeLog
trunk/libstdc++-v3/include/bits/regex_executor.tcc
trunk/libstdc++-v3/include/bits/stl_algobase.h

[Bug libstdc++/71500] regex::icase only works on first character in a range

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #16 from Tim Shen  ---
Author: timshen
Date: Mon Sep 11 19:02:34 2017
New Revision: 251982

URL: https://gcc.gnu.org/viewcvs?rev=251982=gcc=rev
Log:
PR libstdc++/71500
* include/bits/regex_executor.tcc: Support icase in regex_tratis<...>
for back reference matches.
* testsuite/28_regex/regression.cc: Test case.

Modified:
trunk/libstdc++-v3/ChangeLog
trunk/libstdc++-v3/include/bits/regex_executor.tcc
trunk/libstdc++-v3/testsuite/28_regex/regression.cc

[Bug libstdc++/71500] regex::icase only works on first character in a range

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

Jonathan Wakely  changed:

   What|Removed |Added

 Status|UNCONFIRMED |NEW
   Last reconfirmed||2017-08-29
 Ever confirmed|0   |1

--- Comment #15 from Jonathan Wakely  ---


Another testcase from Bug 77492:

#include 
#include 

using namespace std;

void check(const string& s, regex re) {
cout << s << " : " << (regex_match(s, re) ? "Match" : "Nope") << endl;
}

int main() {
regex re1 = regex("([a-z]+) \\1", regex::icase);
check("abc abc", re1);
check("Abc abc", re1);
check("abc Abc", re1);
}

output:
abc abc : Match
Abc abc : Nope
abc Abc : Nope


Tim, your patch didn't change the behaviour for this - is that expected?

[Bug libstdc++/71500] regex::icase only works on first character in a range

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

Jonathan Wakely  changed:

   What|Removed |Added

 CC||flashmozzg at gmail dot com

--- Comment #14 from Jonathan Wakely  ---
*** Bug 77492 has been marked as a duplicate of this bug. ***

[Bug libstdc++/71500] regex::icase only works on first character in a range

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #13 from Tim Shen  ---
Author: timshen
Date: Thu Dec  1 03:03:55 2016
New Revision: 243093

URL: https://gcc.gnu.org/viewcvs?rev=243093=gcc=rev
Log:
PR libstdc++/71500
* include/bits/regex.h (basic_regex::basic_regex): Use ECMAScript
when the syntax is not specified.
* include/bits/regex_compiler.h (_RegexTranslator,
_RegexTranslatorBase): Partially support icase in ranges.
* include/bits/regex_compiler.tcc (_BracketMatcher::_M_apply):
Refactor _M_apply to make the control flow easier to follow, and
call _M_translator._M_match_range as added previously.
* testsuite/28_regex/traits/char/icase.cc: Add new tests.
* testsuite/28_regex/traits/char/user_defined.cc: Add new tests.

Added:
trunk/libstdc++-v3/testsuite/28_regex/traits/char/icase.cc
Modified:
trunk/libstdc++-v3/ChangeLog
trunk/libstdc++-v3/include/bits/regex.h
trunk/libstdc++-v3/include/bits/regex_compiler.h
trunk/libstdc++-v3/include/bits/regex_compiler.tcc
trunk/libstdc++-v3/testsuite/28_regex/traits/char/user_defined.cc

[Bug libstdc++/71500] regex::icase only works on first character in a range

[mwd at md5i dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #12 from Michael Duggan  ---
Just a ping.  I haven't seen a fix for this (even the basic case) in the repo
yet.  I'm going to suggest that you at least install your initial patch, as it
will work in the vast majority of cases.

[Bug libstdc++/71500] regex::icase only works on first character in a range

[mwd at md5i dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #11 from Michael Duggan  ---
"timshen at gcc dot gnu.org"  writes:

> (In reply to Michael Duggan from comment #9)
>> I will make two suggestions.  The initial suggestion is simple enough:
>> Given that regex_traits is mandated to be implemented by the library for
>> char and wchar_t, it would be reasonable, I think, to make the
>> specializations that handled these that go ahead and use the locale.
>> This falls into the "as if" rule, where an implementation is fine as
>> long as it works "as if" the more correct way was implemented.
>
>> The other suggestion is this.  Given that the more correct is "terribly
>> inefficient and impractical", I posit that you have three options: Use
>> the "correct", but "bad", implementation, leave the "incorrect in all
>> cases" implementation in place, or just go ahead and use the locale to
>> implement toggle_case().  Of these three, I think the "incorrect in all
>> cases" option is the worst of all worlds.
>
> In long term I think "toggle_case" or its equivalent should be specified by 
> the
> user-defined traits. I think we can use my toggle_case for now. I'll post a 
> new
> patch to reflect the discussion.
>
> I'll only post the patch after we have an agreement, since I shouldn't bother
> the reviewer (sorry Jon!) too frequently. :P

Sounds good to me.

[Bug libstdc++/71500] regex::icase only works on first character in a range

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

Tim Shen  changed:

   What|Removed |Added

 CC||john at johnmaddock dot co.uk

--- Comment #10 from Tim Shen  ---
(In reply to Michael Duggan from comment #9)
> I will make two suggestions.  The initial suggestion is simple enough:
> Given that regex_traits is mandated to be implemented by the library for
> char and wchar_t, it would be reasonable, I think, to make the
> specializations that handled these that go ahead and use the locale.
> This falls into the "as if" rule, where an implementation is fine as
> long as it works "as if" the more correct way was implemented.

> The other suggestion is this.  Given that the more correct is "terribly
> inefficient and impractical", I posit that you have three options: Use
> the "correct", but "bad", implementation, leave the "incorrect in all
> cases" implementation in place, or just go ahead and use the locale to
> implement toggle_case().  Of these three, I think the "incorrect in all
> cases" option is the worst of all worlds.

In long term I think "toggle_case" or its equivalent should be specified by the
user-defined traits. I think we can use my toggle_case for now. I'll post a new
patch to reflect the discussion.

I'll only post the patch after we have an agreement, since I shouldn't bother
the reviewer (sorry Jon!) too frequently. :P

> (It wouldn't be a bad idea to poke the original authors of the regex
> functionality to see what they think.  Apologies in advance if you were
> one of the authors.)

CC'ed John Maddock, the author of Boost.Regex. :)

[Bug libstdc++/71500] regex::icase only works on first character in a range

[mwd at md5i dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #9 from Michael Duggan  ---
"timshen at gcc dot gnu.org"  writes:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500
>
> --- Comment #8 from Tim Shen  ---
> (In reply to Michael Duggan from comment #7)
>> Hmm...  Okay.  For the sake of argument, I am going to make the
>> following claims: 
>
> Yeah, thanks for the arguments, we should at least get this clear.
>
>> a) Ignoring case _requires_ a locale.  Without a locale, how do you
>>determine the case of a character anyway?  Especially if the
>>character is not a char?  Even std::toupper and std::towuppwer are
>>bound to the "C" locale.
>> 
>>As such, you can't say you're not to use the locale when collate is
>>off.  Otherwise icase wouldn't work ever unless collate was
>>specified.
>
> Not necessarily. My interpretation of "icase" is whether regex should call
> traits_type::translate or traits_type::translate_nocase when comparing two
> characters. No locale is directly involved - a user-defined regex traits type
> may ignore the locale and inject its own weird stuff into translate_nocase.
> It's just, not surprisingly, std::regex_traits "happens to" use locale to
> implement translate_nocase.

Yeah, I think I finally see what you are getting at.

>> b) You can still use regex_traits::transform in an icase scenario.  The
>>rule for [A-B], matching X should be:
>> 
>>  transform(a) <= transform(x) <= transform(b)
>> 
>>In the icase scenario, I would posit that the result of this _or_
>> 
>>  transform(a) <= transform(toggle_case(x)) <= transform(b)
>> 
>>is correct.
>
> +1.
>
> I looked at boost source, it seems that "collate" is interpreted as whether
> regex should call traits_type::transform when doing range matching:
> https://github.com/boostorg/regex/blob/9059bfb5c6287b0c579bfa4be5160b44c8cc2957/include/boost/regex/v4/perl_matcher.hpp#L198
>
> I don't like the way the documentation put it, but the definition above seems
> accurate and clear. transform/collate seems to be an unrelated concern.
>
>
> With above two claims hold, my point is, the way I can think of to implement
> toggle_case:
>   char_type basic_regex<...>::toggle_case(char_type c) {
> const auto& ctype =
> std::use_facet(this->_M_traits.getloc());
> auto lower = ctype.tolower(c);
> if (lower == c) return ctype.toupper(c);
> return lower;
>   }
>
> it uses locale's definition of uppercase/lowercase, not translate_nocase's
> definition. This result might surprise a picky user.
>
> There is a correct way to implement this:
>   if (icase)
> c = traits.translate_nocase(c);
>   else
> c=  traits.translate(c);
>   for (pair range : regex.range_set)
> for (char_type e = range.first; e != range.second+1; ++e) {
>   if (icase)
> e = traits.translate_nocase(e);
>   else
> e = traits.translate(e);
>   if (collate) {
> if (traits.transform(e) == traits.transform(c))
>   return true;
>   } else {
> if (e == c)
>   return true;
>   }
> }
>   }
>   return false;
>
> But it's terribly inefficient and not practical at all.

I will make two suggestions.  The initial suggestion is simple enough:
Given that regex_traits is mandated to be implemented by the library for
char and wchar_t, it would be reasonable, I think, to make the
specializations that handled these that go ahead and use the locale.
This falls into the "as if" rule, where an implementation is fine as
long as it works "as if" the more correct way was implemented.

The other suggestion is this.  Given that the more correct is "terribly
inefficient and impractical", I posit that you have three options: Use
the "correct", but "bad", implementation, leave the "incorrect in all
cases" implementation in place, or just go ahead and use the locale to
implement toggle_case().  Of these three, I think the "incorrect in all
cases" option is the worst of all worlds.

(It wouldn't be a bad idea to poke the original authors of the regex
functionality to see what they think.  Apologies in advance if you were
one of the authors.)

[Bug libstdc++/71500] regex::icase only works on first character in a range

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #8 from Tim Shen  ---
(In reply to Michael Duggan from comment #7)
> Hmm...  Okay.  For the sake of argument, I am going to make the
> following claims: 

Yeah, thanks for the arguments, we should at least get this clear.

> a) Ignoring case _requires_ a locale.  Without a locale, how do you
>determine the case of a character anyway?  Especially if the
>character is not a char?  Even std::toupper and std::towuppwer are
>bound to the "C" locale.
> 
>As such, you can't say you're not to use the locale when collate is
>off.  Otherwise icase wouldn't work ever unless collate was
>specified.

Not necessarily. My interpretation of "icase" is whether regex should call
traits_type::translate or traits_type::translate_nocase when comparing two
characters. No locale is directly involved - a user-defined regex traits type
may ignore the locale and inject its own weird stuff into translate_nocase.
It's just, not surprisingly, std::regex_traits "happens to" use locale to
implement translate_nocase.

> b) You can still use regex_traits::transform in an icase scenario.  The
>rule for [A-B], matching X should be:
> 
>  transform(a) <= transform(x) <= transform(b)
> 
>In the icase scenario, I would posit that the result of this _or_
> 
>  transform(a) <= transform(toggle_case(x)) <= transform(b)
> 
>is correct.

+1.

I looked at boost source, it seems that "collate" is interpreted as whether
regex should call traits_type::transform when doing range matching:
https://github.com/boostorg/regex/blob/9059bfb5c6287b0c579bfa4be5160b44c8cc2957/include/boost/regex/v4/perl_matcher.hpp#L198

I don't like the way the documentation put it, but the definition above seems
accurate and clear. transform/collate seems to be an unrelated concern.


With above two claims hold, my point is, the way I can think of to implement
toggle_case:
  char_type basic_regex<...>::toggle_case(char_type c) {
const auto& ctype =
std::use_facet(this->_M_traits.getloc());
auto lower = ctype.tolower(c);
if (lower == c) return ctype.toupper(c);
return lower;
  }

it uses locale's definition of uppercase/lowercase, not translate_nocase's
definition. This result might surprise a picky user.

There is a correct way to implement this:
  if (icase)
c = traits.translate_nocase(c);
  else
c=  traits.translate(c);
  for (pair range : regex.range_set)
for (char_type e = range.first; e != range.second+1; ++e) {
  if (icase)
e = traits.translate_nocase(e);
  else
e = traits.translate(e);
  if (collate) {
if (traits.transform(e) == traits.transform(c))
  return true;
  } else {
if (e == c)
  return true;
  }
}
  }
  return false;

But it's terribly inefficient and not practical at all.

[Bug libstdc++/71500] regex::icase only works on first character in a range

[mwd at md5i dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #7 from Michael Duggan  ---
"timshen at gcc dot gnu.org"  writes:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500
>
> --- Comment #6 from Tim Shen  ---
> (In reply to mwd from comment #5)
>> All of the ECMAScript engines I have found work with this , and the
>> ECMAScript specs seem to imply that this should work as well.
>
> I think you are right.
>
> According to ECMAScript 262 6th edition [21.2.2.8.1]:
> 5. If invert is false, then
> a. If there does not exist a member a of set A such that Canonicalize(a) 
> is
> cc, return failure.
>
> , when creating the CharSet A, ignorecase is not taken into consideration at
> all; rather, when matching a character against a range, both the character and
> the candidate from the range is "Canonialized" and compared.
>
> Ideally I would implement this as (which is similar to your suggestion):
>   auto toggle_case(auto c) {
> if (isupper(c)) return tolower(c);
> if (islower(c)) return toupper(c);
> return c;
>   }
>
>   if (range.first <= c && c < range.second) { ... }
>   else if (icase && (range.first <= toggle_case(c) && toggle_case(c) <
> range.second)) { ... }
>
> The problem is I'm not sure how to implement this, since:
> When collate is off, locale related function like tolower and toupper should
> not be called; when collate is on, everything should go through
> regex_traits::transform, which doesn't care about icase.

Hmm...  Okay.  For the sake of argument, I am going to make the
following claims: 

a) Ignoring case _requires_ a locale.  Without a locale, how do you
   determine the case of a character anyway?  Especially if the
   character is not a char?  Even std::toupper and std::towuppwer are
   bound to the "C" locale.

   As such, you can't say you're not to use the locale when collate is
   off.  Otherwise icase wouldn't work ever unless collate was
   specified.

b) You can still use regex_traits::transform in an icase scenario.  The
   rule for [A-B], matching X should be:

 transform(a) <= transform(x) <= transform(b)

   In the icase scenario, I would posit that the result of this _or_

 transform(a) <= transform(toggle_case(x)) <= transform(b)

   is correct.

I don't mind if these claims are refuted, but I think I'd need the
refutation explained to me.

[Bug libstdc++/71500] regex::icase only works on first character in a range

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #6 from Tim Shen  ---
(In reply to mwd from comment #5)
> All of the ECMAScript engines I have found work with this , and the
> ECMAScript specs seem to imply that this should work as well.

I think you are right.

According to ECMAScript 262 6th edition [21.2.2.8.1]:
5. If invert is false, then
a. If there does not exist a member a of set A such that Canonicalize(a) is
cc, return failure.

, when creating the CharSet A, ignorecase is not taken into consideration at
all; rather, when matching a character against a range, both the character and
the candidate from the range is "Canonialized" and compared.

Ideally I would implement this as (which is similar to your suggestion):
  auto toggle_case(auto c) {
if (isupper(c)) return tolower(c);
if (islower(c)) return toupper(c);
return c;
  }

  if (range.first <= c && c < range.second) { ... }
  else if (icase && (range.first <= toggle_case(c) && toggle_case(c) <
range.second)) { ... }

The problem is I'm not sure how to implement this, since:
When collate is off, locale related function like tolower and toupper should
not be called; when collate is on, everything should go through
regex_traits::transform, which doesn't care about icase.

libc++ 3.8.0 accepts the regex, but prints:
aaa : Nope
AAA : Nope
fff : Nope
FFF : Nope
ttt : Nope
TTT : Nope
uuu : Nope
UUU : Nope
ggg : Nope
GGG : Nope

which is similar to what I did previously.

I think this is a design flaw in regex_traits, and the Boost behavior is
slightly better (although all of us are broken :P).

[Bug libstdc++/71500] regex::icase only works on first character in a range

[mwd at cert dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #5 from mwd at cert dot org ---
All of the ECMAScript engines I have found work with this , and the ECMAScript
specs seem to imply that this should work as well.

[Bug libstdc++/71500] regex::icase only works on first character in a range

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #4 from Tim Shen  ---
(In reply to Michael Duggan from comment #3)
> regex re1 = regex("[T-f]+", regex::icase);

This regex actually doesn't compile in Boost, since boost interpret icase as
"transforming [T-f] to [t-f]", then throw an invalid range exception. libstdc++
with my previous change treat [t-f] as an empty range, which doesn't do harm,
but it'd better throw an exception.

I haven't try MSVC or libc++.

[Bug libstdc++/71500] regex::icase only works on first character in a range

[mwd at md5i dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

--- Comment #3 from Michael Duggan  ---
Still fails for the following code:

#include 
#include 
#include 

using namespace std;

void check(const string& s, regex re) {
cout << s << " : " << (regex_match(s, re) ? "Match" : "Nope") << endl;
}

int main() {
regex re1 = regex("[T-f]+", regex::icase);
check("aaa", re1);  /* expect match */
check("AAA", re1);  /* expect match */
check("fff", re1);  /* expect match */
check("FFF", re1);  /* expect match */
check("ttt", re1);  /* expect match */
check("TTT", re1);  /* expect match */
check("uuu", re1);  /* expect match */
check("UUU", re1);  /* expect match */
check("ggg", re1);  /* expect no match */
check("GGG", re1);  /* expect no match */
}

Current output:

aaa : Nope
AAA : Nope
fff : Nope
FFF : Nope
ttt : Nope
TTT : Nope
uuu : Nope
UUU : Nope
ggg : Nope
GGG : Nope

[Bug libstdc++/71500] regex::icase only works on first character in a range

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

Tim Shen  changed:

   What|Removed |Added

 CC||timshen at gcc dot gnu.org

--- Comment #2 from Tim Shen  ---
(In reply to Michael Duggan from comment #1)
> I can confirm this issue exists in debian's libstdc++-6-dev (6.1.1-5)
> package.
> 
> I've done some tracing, and here is what I have been able to determine:
> 
> (All of the below refers to functions in bits/regex_compiler.tcc.)
> 

Thanks for the investigation!

I post a patch here: https://gcc.gnu.org/ml/libstdc++/2016-06/msg00012.html

> When std::__detail::_BracketMatcher false>::_M_apply is called, _M_char_set contains just {'a'}, and
> _M_range_set contains {{first='A', second='F'}}.  

This is not expected. _M_char_set should be empty, since in the bracket
expression there is only a range A-F. This is due to a bug where __last_char is
not defined correctly.

After fixing that, the output should be:
aaa : Nope
AAA : Match
fff : Nope
FFF : Match
, which is incorrect in an expected way :).

Then it's easy to fix - simply change _RegexTranslator::_M_transform to
consider icase first by calling _M_translate.

[Bug libstdc++/71500] regex::icase only works on first character in a range

[mwd at md5i dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71500

Michael Duggan  changed:

   What|Removed |Added

 CC||mwd at md5i dot com

--- Comment #1 from Michael Duggan  ---
I can confirm this issue exists in debian's libstdc++-6-dev (6.1.1-5) package.

I've done some tracing, and here is what I have been able to determine:

(All of the below refers to functions in bits/regex_compiler.tcc.)

When std::__detail::_BracketMatcher::_M_apply is called, _M_char_set contains just {'a'}, and _M_range_set
contains {{first='A', second='F'}}.  

When looking up a character in the _M_char_set, the character is lowercased
(because __icase is true) before looking it up in the set.  This is how 'A' and
'a' succeed.

When looking up 'F', the character is not found in the _M_char_set, so the
_M_range_set is checked.  I don't know what the purpose of
_M_translator._M_transform(__ch) is, but since __collate is false, it does
nothing, leaving the character (__s) as 'F'.  It then checks that 'F' is
between 'A' and 'F', which is true.  Success.

When looking up 'f', the character is not found in the _M_char_set, so the
_M_range_set is checked.  'f' is not found to be between 'A' and 'F', so the
match fails.

When the regex is case insensitive, I believe the following has to happen. 
Since it is mostly futile to lower-case a range ([T-f], for example), I think a
candidate char should probably be lower-cased and checked against a range set,
and if that fails, upper-cased and checked against a range set.

That said, any solution that works would be good.

(Note: The calls to _M_apply in the test case will happen when building the
_BracketMatcher's _M_cache, not when the actual regex_match happens.)