`<regex>`: Equivalence classes have unexpected behavior with `std::wregex`

[StephanTLavavej]

Repros with VS 2022 17.14 Preview 4 with microsoft/STL main, including #5392. Tracked by internal VSO-127463 / AB#127463 , originally reported by an external user through the defunct Microsoft Connect site on 2015-06-02.

C:\Temp>type meow.cpp

#include <locale>
#include <print>
#include <regex>
#include <string>
using namespace std;

[[nodiscard]] string escape_wide(const wstring& wstr) {
    string ret{R"(L")"};
    for (const auto& wch : wstr) {
        ret += format(R"(\x{:x})", static_cast<unsigned short>(wch));
    }
    ret += R"(")";
    return ret;
}

void display_result(const wstring& wstr, const wstring& pattern) {
    const locale loc{"fr-FR"};

    wregex rgx;
    rgx.imbue(loc);
    rgx.assign(pattern, regex_constants::icase | regex_constants::collate);

    const bool result = regex_match(wstr, rgx);

    regex_traits<wchar_t> tr;
    tr.imbue(loc);
    const wstring primary_sort_key = tr.transform_primary(wstr.begin(), wstr.end());

    println("wstr: {}; result: {:>5}; primary_sort_key: {}", escape_wide(wstr), result, escape_wide(primary_sort_key));
}

int main() {
    display_result(L"E", L"[[=e=]]");
    display_result(L"\u00C8", L"[[=e=]]"); // LATIN CAPITAL LETTER E WITH GRAVE
    display_result(L"\u00C9", L"[[=e=]]"); // LATIN CAPITAL LETTER E WITH ACUTE
    display_result(L"\u00CA", L"[[=e=]]"); // LATIN CAPITAL LETTER E WITH CIRCUMFLEX

    display_result(L"e", L"[[=e=]]");
    display_result(L"\u00E8", L"[[=e=]]"); // LATIN SMALL LETTER E WITH GRAVE
    display_result(L"\u00E9", L"[[=e=]]"); // LATIN SMALL LETTER E WITH ACUTE
    display_result(L"\u00EA", L"[[=e=]]"); // LATIN SMALL LETTER E WITH CIRCUMFLEX
}

C:\Temp>cl /EHsc /nologo /W4 /std:c++latest /MTd /Od meow.cpp && meow
meow.cpp
wstr: L"\x45"; result:  true; primary_sort_key: L"\xe\x21\x1\x1\x1\x1\x0"
wstr: L"\xc8"; result: false; primary_sort_key: L"\xe\x21\x1\xf\x1\x1\x1\x0"
wstr: L"\xc9"; result: false; primary_sort_key: L"\xe\x21\x1\xe\x1\x1\x1\x0"
wstr: L"\xca"; result: false; primary_sort_key: L"\xe\x21\x1\x12\x1\x1\x1\x0"
wstr: L"\x65"; result:  true; primary_sort_key: L"\xe\x21\x1\x1\x1\x1\x0"
wstr: L"\xe8"; result: false; primary_sort_key: L"\xe\x21\x1\xf\x1\x1\x1\x0"
wstr: L"\xe9"; result: false; primary_sort_key: L"\xe\x21\x1\xe\x1\x1\x1\x0"
wstr: L"\xea"; result: false; primary_sort_key: L"\xe\x21\x1\x12\x1\x1\x1\x0"

The user expects regex_match to always return true here.

I don't understand why LCMapStringEx with LCMAP_SORTKEY is producing these primary sort keys. Are we supposed to be passing extra flags to ignore diacritics?

[muellerj2]

Are we supposed to be passing extra flags to ignore diacritics?

Yes.

For purposes of collation order, a character is assigned a number of sorting weights. Some of these underlying sorting weights also leak into the description of LCMapStringEx. For example, the description for the NORM_IGNORENONSPACE flag states:

NORM_IGNORENONSPACE ignores any secondary distinction, whether it is a diacritic or not. [...] LINGUISTIC_IGNOREDIACRITIC causes the function to ignore only actual diacritics, instead of ignoring the second sorting weight.

transform() is supposed to produce a sort key that considers all of these sorting weights.

transform_primary(), however, is supposed to return a primary sort key. A primary sort key is derived from the primary (first) sorting weight only while ignoring all the others. That said, we probably want to choose linguistically more accurate options for a particular locale than to just neglect all the non-primary weights.

I already wrote in #5291 (comment):

If we want to implement the specification, we should probably add variants of _Strxfrm() and _Wcsxfrm() to the import library that call __crtLCMapStringA/W with appropriate flags for non-C locales (maybe LCMAP_SORTKEY | LINGUISTIC_IGNORECASE | LINGUISTIC_IGNOREDIACRITIC | NORM_IGNOREKANA | NORM_IGNOREWIDTH or something similar).

For the "C" locale, the best we can probably do is to convert all characters to lower or upper case and return that as the sort key.

[muellerj2]

Since equivalence classes are inherited from POSIX, I checked what the POSIX standard says about the sorting weights in the C locale (or, more accurately, the POSIX locale). My reading is that all characters should be assigned a unique primary weight. This would mean that even "a" and "A" do not have the same primary sort key. A quick test with grep seems to confirm that.

However, this is somewhat inconsistent with the general traits requirements of transform_primary() in [re.req]/20 that require that transform_primary() must not consider character case.

I assumed these general traits requirements when I implemented #5392. If these are actually not true, then the implementation has to be fixed in icase mode.

[muellerj2]

I think the traits requirement in [re.req]/20 is wrong for the C locale and the primary sort key according to POSIX is correct.

In the C locale, this is the collation order for alphabetic characters:

A <= B <= ... <= Z <= ... <= a <= b <= ... <= z 

This collation order based on all sorting weights should be consistent with the order that is based on the primary weight only. This means that all these relations should also hold when we compare primary sort keys.

If we also impose that primary sort keys compare equal for lower and upper case versions of the same character, we get

A = B = ... = Z = ... = a = b = ... = z

So all alphabetic characters would be assigned the same primary sort key. This is clearly not what we want.

This means that we also have to fix the processing of equivalences in the parser by adding a character translation phase before calling transform_primary().