Bug 224733 – Refactor sorted array mapping machinery in LocaleToScriptMapping.cpp for reuse elsewhere

• Status: RESOLVED
• Resolution: FIXED
• Component: Web Template Framework

[Darin Adler]

Refactor sorted array mapping machinery in LocaleToScriptMapping.cpp for reuse elsewhere

[Darin Adler]

Created attachment 426382 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 426382 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=426382&action=review

> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:231
> +    static const SortedArrayMap map { scriptNameCodeList };

Can we make it constexpr? This map becomes runtime constructed one so that this cannot be used in multithreaded case without call_once and LazyMeverDestroyed.

[Darin Adler]

Comment on attachment 426382 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=426382&action=review

>> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:231
>> +    static const SortedArrayMap map { scriptNameCodeList };
> 
> Can we make it constexpr? This map becomes runtime constructed one so that this cannot be used in multithreaded case without call_once and LazyMeverDestroyed.

That might be difficult:

1) I don’t think I can use references or pointers in constexpr code, but maybe I can figure it out.

2) We want to run one-time code to check the sorting and uniqueness of keys in the map in debug builds when this is constructed. Not sure I can do that in a constexpr constructor.

Your point about making sure it’s thread-safe is a good one. I am looking for a good solution. Would appreciate your advice if you have ideas.

[Darin Adler]

Maybe I can make it constexpr with the array as a deduced template argument? If I could, then I could use call_once in the constructor to do the one-time sorted checking. But I don’t think template arguments can be arrays of such complex types.

[Darin Adler]

(In reply to Darin Adler from comment #3)
> 2) We want to run one-time code to check the sorting and uniqueness of keys
> in the map in debug builds when this is constructed. Not sure I can do that
> in a constexpr constructor.

C++20 has constexpr std::is_sorted; we could check the sorting at compile time if we had that.

[Darin Adler]

Hope that wouldn't make us compile too slowly, but it would be nice!

[Darin Adler]

Created attachment 426385 [details]
Patch

[Darin Adler]

New version of the patch solves the thread safety problem by not using globals for SortedArrayMap objects, which are simple adapters. Still probably doesn't have includes right for non-unified builds. Also used this in one place in WebKit as a test for wider applicability.

Backed off using KeyValuePair. Even though the member names are much nicer, std::pair handles generic programming much better, and it would be considerable work to fix KeyValuePair to remedy those problems.

Yusuke, hoping for more feedback from you.

[Darin Adler]

Created attachment 426386 [details]
Patch

[Darin Adler]

Created attachment 426387 [details]
Patch

[Darin Adler]

Created attachment 426388 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 426382 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=426382&action=review

>>> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:231
>>> +    static const SortedArrayMap map { scriptNameCodeList };
>> 
>> Can we make it constexpr? This map becomes runtime constructed one so that this cannot be used in multithreaded case without call_once and LazyMeverDestroyed.
> 
> That might be difficult:
> 
> 1) I don’t think I can use references or pointers in constexpr code, but maybe I can figure it out.
> 
> 2) We want to run one-time code to check the sorting and uniqueness of keys in the map in debug builds when this is constructed. Not sure I can do that in a constexpr constructor.
> 
> Your point about making sure it’s thread-safe is a good one. I am looking for a good solution. Would appreciate your advice if you have ideas.

1) We can use references in constexpr!
2) If we construct it in constexpr, then it is called only at compile-time, and one time per map since we are putting it in cpp file.

I've tried making it constexpr by implementing adjacent_find and is_sorted for constexpr (since it becomes constexpr only after C++20 unfortunately. But I think adding an implementation for this debug purpose would be nice since the function is fairly small).
And I've ensured that this can be a constexpr :)
I think this is really nice: it becomes compile-error when the conditions are not met :D

There are several notes.

1. After C++17, lambda can be a constexpr! So we can use lambda in constexpr freely :D
2. After C++17, std::begin and std::end are constexpr so we can use it too!


   75 template<typename Iterator, typename Predicate>
   76 constexpr Iterator adjacentFindConstexpr(Iterator begin, Iterator end, Predicate predicate)
   77 {
   78     if (begin == end)
   79         return end;
   80     auto current = begin;
   81     auto previous = current;
   82     ++current;
   83     while (current != end) {
   84         if (predicate(*previous, *current))
   85             return previous;
   86         previous = current;
   87         ++current;
   88     }
   89     return end;
   90 }
   91
   92 template<typename Iterator, typename Predicate>
   93 constexpr bool isSortedConstexpr(Iterator begin, Iterator end, Predicate predicate)
   94 {
   95     return adjacentFindConstexpr(begin, end, [&](auto& a, auto& b) {
   96         return !predicate(a, b);
   97     }) == end;
   98 }
   99
  100 template<typename ArrayType>
  101 constexpr SortedArrayMap<ArrayType>::SortedArrayMap(const ArrayType& array)
  102     : m_array { array }
  103 {
  104     ASSERT_UNDER_CONSTEXPR_CONTEXT(isSortedConstexpr(std::begin(array), std::end(array), [] (auto& a, auto b) {
  105         return a.first < b.first;
  106     }));
  107     ASSERT_UNDER_CONSTEXPR_CONTEXT(adjacentFindConstexpr(std::begin(array), std::end(array), [] (auto& a, auto& b) {
  108         return a.first == b.first;
  109     }) == std::end(array));
  110 }

And using it via,

   39 static constexpr std::pair<unsigned, unsigned> test[] = {
   40     { 0, 0 },
   41     { 1, 1 },
   42 };
   43
   44 static constexpr SortedArrayMap mapping { test };

This completely works! L44 does not specify array type in SortedArrayMap<XXX>'s XXX place since we can leverage C++17 template type deduction!
This avoids writing array-size explicitly, so everything works well without specifying size etc...

[Yusuke Suzuki]

Comment on attachment 426382 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=426382&action=review

>>>> Source/WebCore/platform/text/LocaleToScriptMapping.cpp:231
>>>> +    static const SortedArrayMap map { scriptNameCodeList };
>>> 
>>> Can we make it constexpr? This map becomes runtime constructed one so that this cannot be used in multithreaded case without call_once and LazyMeverDestroyed.
>> 
>> That might be difficult:
>> 
>> 1) I don’t think I can use references or pointers in constexpr code, but maybe I can figure it out.
>> 
>> 2) We want to run one-time code to check the sorting and uniqueness of keys in the map in debug builds when this is constructed. Not sure I can do that in a constexpr constructor.
>> 
>> Your point about making sure it’s thread-safe is a good one. I am looking for a good solution. Would appreciate your advice if you have ideas.
> 
> 1) We can use references in constexpr!
> 2) If we construct it in constexpr, then it is called only at compile-time, and one time per map since we are putting it in cpp file.
> 
> I've tried making it constexpr by implementing adjacent_find and is_sorted for constexpr (since it becomes constexpr only after C++20 unfortunately. But I think adding an implementation for this debug purpose would be nice since the function is fairly small).
> And I've ensured that this can be a constexpr :)
> I think this is really nice: it becomes compile-error when the conditions are not met :D
> 
> There are several notes.
> 
> 1. After C++17, lambda can be a constexpr! So we can use lambda in constexpr freely :D
> 2. After C++17, std::begin and std::end are constexpr so we can use it too!
> 
> 
>    75 template<typename Iterator, typename Predicate>
>    76 constexpr Iterator adjacentFindConstexpr(Iterator begin, Iterator end, Predicate predicate)
>    77 {
>    78     if (begin == end)
>    79         return end;
>    80     auto current = begin;
>    81     auto previous = current;
>    82     ++current;
>    83     while (current != end) {
>    84         if (predicate(*previous, *current))
>    85             return previous;
>    86         previous = current;
>    87         ++current;
>    88     }
>    89     return end;
>    90 }
>    91
>    92 template<typename Iterator, typename Predicate>
>    93 constexpr bool isSortedConstexpr(Iterator begin, Iterator end, Predicate predicate)
>    94 {
>    95     return adjacentFindConstexpr(begin, end, [&](auto& a, auto& b) {
>    96         return !predicate(a, b);
>    97     }) == end;
>    98 }
>    99
>   100 template<typename ArrayType>
>   101 constexpr SortedArrayMap<ArrayType>::SortedArrayMap(const ArrayType& array)
>   102     : m_array { array }
>   103 {
>   104     ASSERT_UNDER_CONSTEXPR_CONTEXT(isSortedConstexpr(std::begin(array), std::end(array), [] (auto& a, auto b) {
>   105         return a.first < b.first;
>   106     }));
>   107     ASSERT_UNDER_CONSTEXPR_CONTEXT(adjacentFindConstexpr(std::begin(array), std::end(array), [] (auto& a, auto& b) {
>   108         return a.first == b.first;
>   109     }) == std::end(array));
>   110 }
> 
> And using it via,
> 
>    39 static constexpr std::pair<unsigned, unsigned> test[] = {
>    40     { 0, 0 },
>    41     { 1, 1 },
>    42 };
>    43
>    44 static constexpr SortedArrayMap mapping { test };
> 
> This completely works! L44 does not specify array type in SortedArrayMap<XXX>'s XXX place since we can leverage C++17 template type deduction!
> This avoids writing array-size explicitly, so everything works well without specifying size etc...

And if we use something like,

   39 static constexpr std::pair<unsigned, unsigned> test[] = {
   40     { 1, 0 },
   41     { 1, 1 },
   42 };
   43
   44 static constexpr SortedArrayMap mapping { test };

We can get awesome compile-error since this doesn't meet sorted array's ASSERT_UNDER_CONSTEXPR_CONTEXT.

/Volumes/Data/OpenSource/Source/WTF/wtf/SortedArrayMap.cpp:44:33: error: constexpr variable 'mapping' must be initialized by a constant expression
static constexpr SortedArrayMap mapping { test };
                                ^~~~~~~~~~~~~~~~
In file included from /Volumes/Data/OpenSource/Source/WTF/wtf/SortedArrayMap.cpp:28:
/Volumes/Data/OpenSource/Source/WTF/wtf/SortedArrayMap.h:104:5: note: non-constexpr function 'WTFReportAssertionFailure' cannot be used in a constant expression
    ASSERT_UNDER_CONSTEXPR_CONTEXT(isSortedConstexpr(std::begin(array), std::end(array), [] (auto& a, auto b) {
    ^
In file included from /Volumes/Data/OpenSource/Source/WTF/wtf/SortedArrayMap.cpp:27:
In file included from /Volumes/Data/OpenSource/Source/WTF/config.h:31:
In file included from /Volumes/Data/OpenSource/WebKitBuild/Debug/usr/local/include/wtf/FastMalloc.h:26:
In file included from /Volumes/Data/OpenSource/WebKitBuild/Debug/usr/local/include/wtf/StdLibExtras.h:32:
/Volumes/Data/OpenSource/WebKitBuild/Debug/usr/local/include/wtf/Assertions.h:354:9: note: expanded from macro 'ASSERT_UNDER_CONSTEXPR_CONTEXT'
        WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
        ^
/Volumes/Data/OpenSource/Source/WTF/wtf/SortedArrayMap.cpp:44:33: note: in call to 'SortedArrayMap(test)'
static constexpr SortedArrayMap mapping { test };
                                ^
In file included from /Volumes/Data/OpenSource/Source/WTF/wtf/SortedArrayMap.cpp:27:
In file included from /Volumes/Data/OpenSource/Source/WTF/config.h:31:
In file included from /Volumes/Data/OpenSource/WebKitBuild/Debug/usr/local/include/wtf/FastMalloc.h:26:
In file included from /Volumes/Data/OpenSource/WebKitBuild/Debug/usr/local/include/wtf/StdLibExtras.h:32:
/Volumes/Data/OpenSource/WebKitBuild/Debug/usr/local/include/wtf/Assertions.h:204:25: note: declared here
WTF_EXPORT_PRIVATE void WTFReportAssertionFailure(const char* file, int line, const char* function, const char* assertion);
                        ^
1 error generated.
** BUILD FAILED **

[Darin Adler]

Thanks for the encouragement, and for the constexpr implementations of is_sorted and adjacent_find.

[Darin Adler]

Created attachment 426438 [details]
Patch

[Darin Adler]

Yusuke, took all your suggestions and now this seems ready to go! Would you be willing to review?

[Yusuke Suzuki]

Comment on attachment 426438 [details]
Patch

r=me!

[Darin Adler]

Committed r276303 (236785@main): <https://commits.webkit.org/236785@main>

[Ling Ho]

rdar://76898173